合計が最大となる部分配列を見つけるJavaScript関数の実装方法

正の数と負の数が混在する数値配列を引数として受け取るJavaScript関数を作成することを考えます。この関数の目的は、配列の中から任意の長さの部分配列(連続する要素の集まり)を抜き出し、その要素を合計したときに最大となるものを見つけることです。そして、見つかった部分配列の合計値を返します。

例

入力配列が次の通りだとします。

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

このとき期待される出力は以下の通りです。

const output = 6;

[4, -1, 2, 1] を選んだ場合の合計が 6 となり、これが取り得る最大値だからです。

解法：カダネのアルゴリズム

この種の問題は「カダネのアルゴリズム」と呼ばれる定番の手法で解くのが最も効率的です。考え方はシンプルで、配列を先頭から順に走査しながら、次の2つの値を更新していきます。

• sum: 現在位置で終わる部分配列の合計の最大値。「直前までの合計に現在の要素を足す」か「現在の要素だけで新しく始める」かの大きい方を採用します。
• max: これまでに登場した sum の最大値(最終的な答えとなります)。

累積合計が負になるような選択は常に不利なため、Math.max() を使うことで「区間をそこで切り替える」判断が自動的に行われます。

コード例

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

const maxSubArray = (arr = []) => {
    let sum = arr[0], max = arr[0];
    for (let i = 1; i < arr.length; ++i){
        sum = Math.max(sum + arr[i], arr[i]);
        max = Math.max(max, sum);
    }
    return max;
};

console.log(maxSubArray(arr));

出力

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

6

計算量について

この実装は配列を1回だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) で済みます。すべての部分配列を総当たりで調べる O(n²) や O(n³) の素朴なアプローチと比べ、要素数の多い配列でも高速に動作する点が大きなメリットです。