C++で厳密に減少する部分配列の個数を効率的に求める方法

厳密に減少する部分配列とは

配列 A が与えられたとき、長さが 2 以上の「厳密に減少する部分配列」が全部でいくつ存在するかを求めます。ここで「厳密に減少する」とは、隣り合う要素が必ず左から右へ向かって小さくなっていることを意味します。

例として、A = [100, 3, 1, 15] を考えてみましょう。この場合、条件を満たす部分配列は [100, 3]、[100, 3, 1]、[3, 1] の 3 つとなるため、答えは 3 です。

アルゴリズムの考え方

すべての部分配列を列挙して一つずつ判定する方法もありますが、計算量が O(n²) となり非効率です。そこで、次のような性質を利用します。

長さ l の連続した減少列が見つかったとき、その中に含まれる長さ 2 以上の減少部分配列の数は l × (l − 1) / 2 で求められます。これは、減少列の中から始点と終点のペアを選ぶ組み合わせの数に相当します。

したがって、配列を一度走査しながら連続する減少列の長さを数え、減少が途切れた時点で l(l − 1)/2 を答えに加算していけば、O(n) の計算量で解くことができます。

C++での実装例

#include <iostream>
using namespace std;

int countSubarrays(int array[], int n) {
    int count = 0;
    int l = 1;
    for (int i = 0; i < n - 1; ++i) {
        if (array[i + 1] < array[i])
            l++;
        else {
            count += (((l - 1) * l) / 2);
            l = 1;
        }
    }
    if (l > 1)
        count += (((l - 1) * l) / 2);
    return count;
}

int main() {
    int A[] = { 100, 3, 1, 13, 8 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Number of decreasing subarrays: " << countSubarrays(A, n);
}

実行結果

Number of decreasing subarrays: 4

コードの解説

変数 l は、現在継続中の減少列の長さを表します。隣接する 2 要素を比較し、array[i + 1] < array[i] が成り立てば減少が続いているので l を 1 増やします。そうでなければ減少列が途切れたため、それまでの長さ l から l(l − 1)/2 を答えに加算し、l を 1 に戻します。

ループ終了後、配列の末尾まで減少列が続いていた場合の分を加算し忘れないよう、l > 1 のときにもう一度加算しています。

例の配列 {100, 3, 1, 13, 8} では、[100, 3, 1] から 3 個、[13, 8] から 1 個の計 4 個が数えられ、実行結果も 4 となります。