【C/C++】最大連続部分配列の合計を求めるプログラム（動的計画法）

整数の配列が与えられたとき、連続する要素の合計の中で最も大きくなるものを見つけ、その値を出力する問題です。これは「最大部分配列和問題」として知られる古典的なアルゴリズム課題の一つです。

この問題は動的計画法（DP）を使うことで効率的に解くことができます。各位置において「現在の位置までの最大合計」を記録していき、それを更新しながら全体の最大値を求めます。これにより、配列内の連続する要素の最大和を線形時間 O(n) で計算できます。

入力：整数の配列 {-2, -3, 4, -1, -2, 1, 5, -3}
出力：部分配列の最大合計：7

アルゴリズム

maxSum(array, n)

入力： メインの配列と、その配列のサイズ。

出力： 部分配列の最大合計。

Begin
    tempMax := array[0]
    currentMax = tempMax
    for i := 1 to n-1, do
        currentMax = maximum of (array[i] and currentMax+array[i])
        tempMax = maximum of (currentMax and tempMax)
    done
    return tempMax
End

アルゴリズムのポイント

このアルゴリズム（カダネのアルゴリズムとしても知られています）では、以下の2つの変数を使用します。

• currentMax： 現在の位置で終わる連続部分配列の最大合計。現在の要素だけを選ぶか、直前の合計に加えるかの大きい方を採用します。
• tempMax： それまでに見つかった全体の最大合計。currentMax が更新されるたびに比較し、より大きい方を保持します。

負の数が含まれる配列でも正しく動作する点が特徴で、すべての要素が負の場合でも、その中で最も大きい1つの要素が答えとして返されます。

C++での実装例

#include<iostream>
using namespace std;
int maxSum( int arr[], int n) {
    int tempMax = arr[0];
    int currentMax = tempMax;
    for (int i = 1; i < n; i++ ) { //最大値を求める
        currentMax = max(arr[i], currentMax+arr[i]);
        tempMax = max(tempMax, currentMax);
    }
    return tempMax;
}
int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = 8;
    cout << "Maximum Sum of the Sub-array is: "<< maxSum( arr, n );
}

実行結果

Maximum Sum of the Sub-array is: 7

この例では、配列 {-2, -3, 4, -1, -2, 1, 5, -3} の中で、{4, -1, -2, 1, 5} の連続した部分配列の合計が 7 となり、これが最大値です。