O(n²)の計算量で最大部分配列の和を求めるC++プログラム（素朴な手法）

本記事では、O(n²)の計算量で配列内の最大部分配列の和を求めるC++プログラムを紹介します。この手法は「素朴な手法（ナイーブ法）」と呼ばれ、あらゆる長さの部分配列を効率よく走査することで最大値を導き出します。

アルゴリズム

開始
    配列の要素を入力として受け取る。
    部分配列の長さを 1 から n まで変化させるループを作成する。
    そのループの中に、さらにネストした別のループを作り、
    その長さにおける最初の部分配列の和を計算する。
    残りの部分配列の和については、直前の和に次の要素を加え、
    ウィンドウから外れる先頭の要素を引くことで効率的に求める。
    求めた値を全体の最大値と比較し、より大きければ更新する。
    最後に、最大の部分配列とその和を出力する。
終了。

アルゴリズムのポイント

この手法の鍵となるのは「スライディングウィンドウ」の考え方です。同じ長さの部分配列を次々と調べる際に、毎回ゼロから合計を計算し直すのではなく、直前の部分配列の和を再利用します。具体的には、新しい要素を加算し、範囲外となる先頭の要素を減算するだけで、次の部分配列の和を O(1) で求められます。これにより、各長さごとの走査が O(n)、長さの組み合わせが n 通りあるため、全体の計算量は O(n²) に収まります。

サンプルコード

#include<iostream>
using namespace std;
int main() {
    int n, i, j, m=-1, s, ini_m, fi_m;
    cout<<"\nEnter the number of data element in the array: ";
    cin>>n;
    int a[n];
    for(i = 0; i < n; i++) {
        cout<<"Enter element "<<i+1<<": ";
        cin>>a[i];
    }
    for(i = 1; i < n+1; i++) {
        s = 0;
        for(j = 0; j < n; j++) {
            if(j < i)
                s += a[j];
            else
                s = s+a[j]-a[j-i];
            if(m< s) {
                ini_m = j-i+1;
                fi_m = j;
                m = s;
            }
        }
    }
    cout<<"\nThe maximum sub array is: ";
    for(i = ini_m; i <= fi_m; i++)
        cout<<a[i]<<" ";
        cout<<"\nThe maximum sub-array sum is: "<<m;
}

実行結果

Enter the number of data element in the array: 10
Enter element 1: 1
Enter element 2: -2
Enter element 3: 3
Enter element 4: -4
Enter element 5: 5
Enter element 6: -6
Enter element 7: 7
Enter element 8: 8
Enter element 9: -9
Enter element 10: 10
The maximum sub array is: 7 8 -9 10
The maximum sub-array sum is: 16

結果の解説と補足

上記の例では、配列 {1, -2, 3, -4, 5, -6, 7, 8, -9, 10} の中から、部分配列 {7, 8, -9, 10} の和である 16 が最大となることが確認できます。

なお、この問題は「カダネのアルゴリズム（Kadane's Algorithm）」を用いれば O(n) の計算量で解くことも可能です。O(n²) の素朴な手法は、アルゴリズムの動作を理解するうえで非常に有用な第一歩ですが、大規模なデータを扱う実運用では、より効率的な手法の採用を検討するとよいでしょう。