二分探索（分割統治）アプローチで最大部分配列の合計を求めるC++プログラム

二分探索は、計算量 O(log n) と非常に高速な探索アルゴリズムで、「分割統治法（divide and conquer）」という原理に基づいて動作します。このアルゴリズムが正しく機能するためには、対象となるデータ集合があらかじめソート済みである必要があります。

二分探索では、データ集合の中央にある要素と目的の要素を比較しながら特定の項目を探します。一致すればそのインデックスを返し、中央の要素の方が大きければ中央より左側の部分配列を、そうでなければ右側の部分配列を探索します。この処理を部分配列に対して繰り返し、探索範囲がゼロになるまで続けます。

本記事で紹介するのは、この分割統治の考え方を応用して、配列の中から合計が最大となる連続した部分配列（最大サブアレイ）を見つけるC++プログラムです。配列を半分ずつに分割しながら再帰的に処理するため、すべてのパターンを総当たりするよりも効率よく答えを求められます（計算量はO(n log n)）。

アルゴリズム

このプログラムは、次の3つの関数とmain関数で構成されています。

1. maximum() ― 2つの整数の最大値を返す

• 引数として整数 val1 と val2 を受け取ります。
• 両者を比較し、大きい方の値を返します。

2. MCS() ― 中央をまたぐ最大合計を求める

配列 array[] と、下限 l・中央 m・上限 h を受け取り、中央の位置 m をまたぐ形の部分配列の最大合計を計算します。

• 変数 s を 0 で、sum_of_left_part を −1 で初期化します。
• i を m から l まで減らしながら s に array[i] を加算し、s が sum_of_left_part より大きければ値を更新します（左側部分の最大合計）。
• s を 0 に戻し、sum_of_right_part を −1 で初期化します。
• i を m+1 から h まで増やしながら同様の処理を行い、右側部分の最大合計を求めます。
• sum_of_left_part ＋ sum_of_right_part を返します。

3. MaximumSum_of_SubArray() ― 再帰的に最大部分配列合計を求める

• l == h（要素が1つだけ）の場合は、array[l] をそのまま返します。
• それ以外の場合は、m = (l + h) / 2 として中央位置を求めます。
• 「左半分の最大合計」「右半分の最大合計」「中央をまたぐ最大合計（MCS）」の3つを maximum() で比較し、最も大きい値を返します。

main() ― 入力と結果の出力

• 要素数 number_of_elements を入力として受け取ります。
• forループで配列 a[] の各要素を順番に入力します。
• MaximumSum_of_SubArray(a, 0, n−1) の結果を「Maximum sum of Sub-Array is: 」として出力します。

サンプルコード

#include<iostream>
using namespace std;

// 2つの整数のうち大きい方を返す関数
int maximum(int val1, int val2) {
    return (val1 > val2)? val1:val2;
}

// 中央の位置mをまたぐ最大合計の部分配列を求める関数
int MCS(int array[], int l, int m, int h) {
    int s = 0;
    int sum_of_left_part = -1;
    // 左側（mからlへ向かって）の累積和の最大値を求める
    for (int i = m; i >= l; i--) {
        s = s + array[i];
        if (s > sum_of_left_part)
            sum_of_left_part = s;
    }
    s = 0;
    int sum_of_right_part = -1;
    // 右側（m+1からhへ向かって）の累積和の最大値を求める
    for (int i = m+1; i <= h; i++) {
        s = s + array[i];
        if (s > sum_of_right_part)
            sum_of_right_part = s;
    }
    // 中央の左右それぞれの最大合計を足して返す
    return sum_of_left_part + sum_of_right_part;
}

// 再帰的に最大部分配列の合計を求める関数
int MaximumSum_of_SubArray(int array[], int l, int h) {
    int m;
    // 要素が1つの場合はその値を返す
    if (l == h)
        return array[l];
    m = (l + h)/2;
    // 「左半分」「右半分」「中央をまたぐケース」の最大値を返す
    return maximum(maximum(MaximumSum_of_SubArray(array, l, m), MaximumSum_of_SubArray(array, m+1, h)), MCS(array, l, m, h));
}

int main() {
    int number_of_elements, i;
    cout<<"Enter the number of elements of array: ";
    cin>> number_of_elements;
    cout<<endl;
    int a[number_of_elements]; // 可変長配列（VLA）
    for(i = 0; i < number_of_elements; i++) {
        cout<<"Enter the element of "<<i+1<<": ";
        cin>>a[i];
    }
    // 最大部分配列の合計を出力
    cout<<"\nMaximum sum of Sub-Array is: "<<MaximumSum_of_SubArray(a, 0, number_of_elements -1);
    return 0;
}

実行結果

Enter the number of elements of array: 5

Enter the element of 1: 12
Enter the element of 2: 45
Enter the element of 3: 56
Enter the element of 4: 48
Enter the element of 5: 75

Maximum sum of Sub-Array is: 236

この例では、配列 {12, 45, 56, 48, 75} のすべての要素を足した 236 が最大部分配列の合計となります。すべての要素が正の値の場合は配列全体の合計が必ず最大になるため、このアルゴリズムの真価が発揮されるのは、負の値が混在する配列を扱うときです。

補足

• サンプルコードでは可変長配列（int a[number_of_elements]）を使用していますが、これはGCCなどコンパイラ固有の拡張機能です。標準規格に厳密に準拠したい場合は、std::vector<int> の使用を推奨します。
• この手法は「最大部分配列問題」を解く古典的な分割統治法であり、単純な全探索のO(n²)よりも高速なO(n log n)で解けるのが大きな利点です。なお、Kadaneのアルゴリズムを使えばO(n)で求解することも可能です。