C++で厳密に増加するサブ配列を数える方法を解説

整数要素を含む配列が与えられたとき、その配列から取り出せるすべてのサブ配列（部分配列）の中で、「厳密に増加している」（すべての要素が直前の要素より大きい）ものの個数を求めるのがこの問題の目的です。条件を満たさないサブ配列は候補から除外します。

ここでのポイントは、サブ配列の先頭2つの要素（0番目と1番目）の時点ですでに増加していない場合、それ以降のチェックを打ち切ることで無駄な計算を省くという効率的なアプローチです。

C++での例

入力: int a[] = {1, 7, 5}

出力: 厳密に増加するサブ配列の数は 1

説明: 考えられるサブ配列は {1,7,5}、{1,7}、{7,5} の3つですが、このうち厳密に増加しているのは {1,7} のみです。

入力: int a[] = {1, 2, 7, 10}

出力: 厳密に増加するサブ配列の数は 6

説明: {1,2}、{1,2,7}、{1,2,7,10}、{2,7}、{2,7,10}、{7,10} の6つすべてが厳密に増加しているため、答えは6になります。

プログラムで使用するアプローチ

• 配列を宣言し、要素を入力した後、そのデータと配列の長さを関数 countIncSubarrays(a, n) に渡して処理を行います。
• 関数内では、まずカウント用の変数を0で初期化します。
• 外側のループで i を 0 から配列の長さまで回します。
• 内側のループで j を i+1 から配列の長さまで回します。
• a[j] が a[j-1] より大きければ count をインクリメントし、そうでなければ break でループを抜けます（増加順序のチェックが失敗したため）。
• main 関数側で関数の戻り値を受け取り、結果として出力します。

C++コード例

#include <iostream>
using namespace std;

int countIncSubarrays(int a[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[j] > a[j - 1])
                count++;
            else
                break;
        }
    }
    return count;
}

int main() {
    int a[] = {1, 2, 7, 10};
    int n = sizeof(a) / sizeof(a[0]);
    int result = countIncSubarrays(a, n);
    cout << "厳密に増加するサブ配列の数は " << result << endl;
    return 0;
}

上記のコードを実行すると、次の出力が得られます。

出力

厳密に増加するサブ配列の数は 6

計算量について

このアルゴリズムの最悪計算量は O(n²) です。ただし、増加が途切れた時点で内側のループを即座に抜けるため、実際の実行時間は入力データの性質（増加区間の長さ）によって大きく短縮されます。単純で理解しやすい実装であり、小〜中規模の配列に対しては十分に実用的な手法です。