最大連続部分配列の総和を求めるアルゴリズム（カデインのアルゴリズム）を解説

最大連続部分配列和とは

整数型の配列が与えられたとき、その中から「連続する要素」を選び、それらの総和が最大となる組み合わせを求める問題です。この最大値を出力として返します。

この問題は、動的計画法（DP）を使うことで効率的に解くことができます。配列を先頭から順に走査しながら「現在の位置で終わる部分配列の最大和」を記録していくことで、各時点における連続する要素の最大合計を求められます。これは一般にカデインのアルゴリズム（Kadane's Algorithm）として知られる手法です。

入力と出力の例

入力：
整数の配列 {-2, -3, 4, -1, -2, 1, 5, -3}

出力：
Maximum Sum of the Subarray is: 7

この例では、「4, -1, -2, 1, 5」という連続した部分配列を選んだときに総和が 7 となり、これが最大となります。

アルゴリズムの考え方

関数 maxSum(array, n) を以下のように定義します。

• 入力： 元の配列と、そのサイズ n。
• 出力： 連続部分配列の最大総和。

処理の流れは次のとおりです。

Begin
   tempMax := array[0]   // 全体の最大和を初期化
   currentMax := tempMax  // 現在位置で終わる部分配列の最大和
   for i := 1 to n-1, do
      currentMax := max(array[i], currentMax + array[i])
      tempMax := max(currentMax, tempMax)
   done
   return tempMax
End

ポイント

• currentMax： 「現在の要素から新しい部分配列を始める」か「直前の部分配列に現在の要素をつなげる」かの、より大きい方を選択します。
• tempMax： これまでに登場した currentMax の最大値を保持し、最終的な答えとなります。

currentMax が負になった場合は、それ以前の要素を引きずるよりも新しい部分配列を始めた方がよい、という判断が自動的に行われるのがこのアルゴリズムの美しいところです。

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

計算量について

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(n)、必要な記憶領域は定数個の変数のみで O(1) となります。すべての部分配列を総当たりで調べる方法（O(n²) や O(n³)）と比べて非常に高速であり、実務や競技プログラミングでも広く使われる定番のテクニックです。