【C++】分割統治法で最大部分配列和を求める方法を解説

正の値と負の値が混在する数列が与えられたとき、その中から「要素が連続する部分配列(サブアレイ)」のうち合計が最大になるものを求める問題を考えます。例えば、数列 {-2, -5, 6, -2, -3, 1, 5, -6} の場合、最大部分配列和は 7 となり、これは {6, -2, -3, 1, 5} の合計に相当します。

この問題は、分割統治法(Divide and Conquer)を用いることで効率的に解くことができます。

アルゴリズムの手順

• 配列を中央で2つに分割する
• 以下の3つの値のうち最大のものを求める
  • 左側の部分配列における最大部分配列和
  • 右側の部分配列における最大部分配列和
  • 中央をまたいで(左右にまたがる)部分配列の最大和

中央をまたぐ最大和は、中央の要素から左方向へ累積和を取りながら最大値を求め、同様に中央+1から右方向へも最大値を求め、その2つを足し合わせることで計算できます。

C++での実装例

#include <iostream>
#include <climits>
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 += arr[i];
        if (sum > left)
            left = sum;
    }
    sum = 0;
    int right = INT_MIN;
    for (int i = m + 1; i <= h; i++) {
        sum += arr[i];
        if (sum > right)
            right = sum;
    }
    return left + right;
}

// 分割統治法による最大部分配列和
int maxSubArraySum(int arr[], int low, int high) {
    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

計算量について

このアルゴリズムの時間計算量は O(n log n) です。配列を再帰的に半分に分割していくため O(log n) 段階の再帰が発生し、各段階で中央をまたぐ和の計算に O(n) の処理が必要になるためです。

なお、動的計画法を利用した「カダネのアルゴリズム(Kadane's Algorithm)」を用いれば、O(n) でこの問題を解くことも可能です。データ量が非常に大きい場合は、こちらの手法を検討するとよいでしょう。