【JavaScript】配列から合計が最大となる連続部分配列を求める方法（カダネのアルゴリズム）

問題の概要

正と負の整数が混在する配列を受け取り、その中から合計が最大となる連続した部分配列を見つけ出して返す、JavaScript関数を作成してみましょう。

配列には負の要素も含まれているため、連続する要素の合計は正にも負にもなり得ます。あらゆる区間の組み合わせの中で最も大きな合計値を持つ部分配列を特定し、その配列自体を返すことがゴールです。

入力例

たとえば、次のような配列を考えてみます。

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

この場合に達成できる最大の合計は 7 であり、出力すべき部分配列は以下のとおりです。

const output = [4, -1, -2, 1, 5];

解決のアプローチ：カダネのアルゴリズム

この問題は古典的な「最大部分配列問題」として知られており、カダネのアルゴリズム（Kadane's Algorithm）を使うことで、O(n) の計算量で効率的に解くことができます。

基本的な考え方はシンプルで、次の2つのルールに集約されます。

• 合計がプラスである限り、そのまま部分配列を伸ばし続ける。
• 合計がマイナスになった瞬間、それを引きずっても得はないため、0にリセットして次の要素から新しい部分配列を始める。

同時に、これまでに見つかった最大の合計と、そのときの開始・終了インデックスを記録しておき、最後にその範囲を切り出します。

コード例

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

const maximumSubarray = (arr = []) => {
    let max = -Infinity;              // 見つかった最大合計
    let currentSum = 0;               // 現在の連続合計
    let maxStartIndex = 0;            // 最大合計となる部分配列の開始位置
    let maxEndIndex = arr.length - 1; // 最大合計となる部分配列の終了位置
    let currentStartIndex = 0;        // 現在走査中の部分配列の開始位置

    arr.forEach((currentNumber, currentIndex) => {
        currentSum += currentNumber;

        // 最大値を更新できたら、範囲ごと記録する
        if (max < currentSum) {
            max = currentSum;
            maxStartIndex = currentStartIndex;
            maxEndIndex = currentIndex;
        }

        // 合計が負になったらリセットし、次の要素から再スタート
        if (currentSum < 0) {
            currentSum = 0;
            currentStartIndex = currentIndex + 1;
        }
    });

    return arr.slice(maxStartIndex, maxEndIndex + 1);
};

console.log(maximumSubarray(arr));

実行結果

コンソールには次のように出力されます。

[ 4, -1, -2, 1, 5 ]

コードのポイント解説

• max：これまでに発見した最大合計。初期値を -Infinity にすることで、すべて負の要素からなる配列にも対応できます。
• currentSum：「現在のインデックスで終わる」連続部分配列の合計を表します。
• maxStartIndex / maxEndIndex：最大合計を達成した区間を記録し、最後に slice() を使って実際の配列を切り出して返します。
• currentStartIndex：合計が負になったタイミングで currentIndex + 1 に移動させることで、新しい候補区間の起点を管理しています。

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(n)、追加で必要なメモリも定数個の変数のみという、非常に効率的な実装になっています。全ての区間を総当たりする素朴な手法（O(n²)〜O(n³)）と比べても、大幅な高速化が期待できるでしょう。