C++のプレフィックス和（累積和）を活用してO(n)で最大部分配列和を求める方法

問題概要

正の整数と負の整数が混在する配列が与えられたとき、その配列の中で合計値が最大となる部分配列（連続した要素の並び）の合計を求める問題です。

例

入力配列が {-12, -5, 4, -1, -7, 1, 8, -3} の場合、合計が最大になる部分配列は {1, 8} となるため、出力は 9 になります。

アルゴリズム

この問題は、プレフィックス和（累積和）を利用することで O(n) の時間計算量で効率的に解くことができます。考え方の核心は、「ある位置 i で終わる部分配列の合計の最大値」は「prefix_sum[i] から、それ以前に現れた最小の累積和を引いた値」で表せるという点です。

具体的な手順は以下の通りです。

• 入力配列のプレフィックス和（累積和）を計算します。

• min_prefix_sum = 0、res = −無限大 として初期化します。

• i = 0 から n−1 までループを回します（n は入力配列のサイズ）。
  

  • cand = prefix_sum[i] − min_prefix_sum を計算します。

  • cand が res（これまでに見つかった最大部分配列和）より大きければ、res を cand で更新します。

  • prefix_sum[i] が min_prefix_sum（これまでの最小累積和）より小さければ、min_prefix_sum を prefix_sum[i] で更新します。

• 最後に res を返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int maximumSumSubarray(int *arr, int n){
    int minPrefixSum = 0;
    int res = numeric_limits<int>::min();
    int prefixSum[n];
    prefixSum[0] = arr[0];
    for (int i = 1; i < n; i++) {
        prefixSum[i] = prefixSum[i - 1] + arr[i];
    }
    for (int i = 0; i < n; i++) {
        res = max(res, prefixSum[i] - minPrefixSum);
        minPrefixSum = min(minPrefixSum, prefixSum[i]);
    }
    return res;
}
int main(){
    int arr[] = {-12, -5, 4, -1, -7, 1, 8, -3};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Result = " << maximumSumSubarray(arr, n) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Result = 9

計算量

• 時間計算量：O(n) — 配列を前処理と本処理の合わせて2回走査するだけです。

• 空間計算量：O(n) — 累積和を格納するための補助配列が必要です。