C++で分割統治法を使って最大部分配列和を求める方法

正と負の値が混在するデータのリストがあるとします。ここで求めるのは、要素が連続している部分配列（サブアレイ）の中で、合計が最大となるものです。例えば、リストが {-2, -5, 6, -2, -3, 1, 5, -6} の場合、最大部分配列和は 7 となり、これは {6, -2, -3, 1, 5} の合計に相当します。

この問題は、分割統治法（Divide and Conquer）を用いることで効率的に解くことができます。基本的な考え方は以下の通りです。

アルゴリズムの手順

• 配列を左右の2つの部分に分割する
• 次の3つの値のうち最大のものを答えとする
  • 左側の部分配列における最大部分配列和
  • 右側の部分配列における最大部分配列和
  • 配列の中央（中間点）をまたいで広がる部分配列の最大和

この処理を再帰的に繰り返すことで、配列全体の最大部分配列和を求められます。計算量は O(n log n) となり、全ての部分配列を単純に調べる O(n²) の方法よりも高速です。

C++での実装例

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b)? a : b;
}

int max(int a, int b, int c) {
    return max(max(a, b), c);
}

// 中央をまたぐ部分配列の最大和を求める関数
int getMaxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0;
    int left = INT_MIN;
    // 中央から左方向へ走査し、左側の最大和を求める
    for (int i = m; i >= l; i--) {
        sum = sum + arr[i];
        if (sum > left)
            left = sum;
    }
    sum = 0;
    int right = INT_MIN;
    // 中央+1から右方向へ走査し、右側の最大和を求める
    for (int i = m+1; i <= h; i++) {
        sum = sum + arr[i];
        if (sum > right)
            right = sum;
    }
    return left + right;
}

// 分割統治法により最大部分配列和を求める関数
int maxSubArraySum(int arr[], int low, int high) {
    // 要素が1つだけの場合はその値自身が答え
    if (low == high)
        return arr[low];
    int mid = (low + high)/2;
    return max(maxSubArraySum(arr, low, mid),
               maxSubArraySum(arr, mid+1, high),
               getMaxCrossingSum(arr, low, mid, high));
}

int main() {
    int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n-1);
    printf("Maximum contiguous sum is %d", max_sum);
}

実行結果

Maximum contiguous sum is 7

このプログラムでは、配列 {-2, -5, 6, -2, -3, 1, 5, -6} を入力とした場合、最大部分配列和として 7 が出力されます。これは {6, -2, -3, 1, 5} の合計と一致しており、アルゴリズムが正しく動作していることが確認できます。

なお、同様の問題はカダネのアルゴリズム（Kadane's Algorithm）を使えば O(n) で解くことも可能ですが、分割統治法は「問題を小さく分割して解く」という考え方を学ぶうえで非常に良い題材となります。