KadaneのアルゴリズムでJavaScriptの最大部分配列和を線形時間で求める方法

問題

正と負の整数が混在する配列 arr を唯一の引数として受け取るJavaScript関数を作成します。

この関数は、配列内の任意の部分配列（連続する要素の集まり）の合計として考えられる最大値を、線形時間 O(n) で返す必要があります。

Kadaneのアルゴリズムの考え方

任意のインデックス i における「局所最大値（local_maximum）」とは、arr[i] 単独の値と、arr[i] + インデックス i-1 の局所最大値 のうち大きい方を指します。

この考え方を配列の先頭から順に適用していけば、配列全体をたった一度の走査で処理するだけで、最大部分配列和を効率よく求めることができます。

入力例と出力例

例えば、関数に次のような配列を渡したとします。

入力

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];

出力

const output = 6;

出力の解説

合計が最大となる部分配列は以下の通りです。

[4, -1, 2, 1]

4 + (-1) + 2 + 1 = 6 となり、この配列で達成可能な最大の部分配列和は6になります。途中に負の要素が含まれていても、それを含めた方が合計が大きくなるケースでは、あえて含めるのが最適解となります。

実装コード

以下が実際のコードです。

const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
const maxSequence = (arr = []) => {
    let currentSum = 0;
    let maxSum = 0;

    for (let elem of arr) {
        const nextSum = currentSum + elem;
        maxSum = Math.max(maxSum, nextSum);
        currentSum = Math.max(nextSum, 0);
    }

    return maxSum;
};
console.log(maxSequence(arr));

出力結果

6

コードのポイント

この実装では、変数 currentSum が「現在位置までの累積和」を表し、負になった時点で 0 にリセットされます。これは、それまでの累積和が以降の部分配列にとって不利にしか働かないためです。一方、maxSum はこれまでに登場した最大の合計を常に記録しており、ループ終了後に答えとして返されます。計算量は O(n)、追加メモリも O(1) と非常に効率的です。