JavaScriptで合計が0以上となる最長部分配列を見つけるアルゴリズム

問題の概要

今回は、-1から1の範囲の整数のみを含む配列を受け取り、その中から合計が0以上になる最長の連続する部分配列（サブアレイ）の長さを返すJavaScript関数を作成します。

一見単純な問題に見えますが、全ての組み合わせを総当たりで調べると計算量がO(n²)となり、配列が大きくなると非効率です。そこで本記事では、累積和（プレフィックスサム）の考え方を活用し、線形時間O(n)で解くスマートな手法を紹介します。

解法のコード

const arr = [-1, -1, 0, 1, 1, -1, -1, -1];
const longestPositiveSum = (arr = []) => {
    let sum = 0;
    let maxslice = 0;
    let length = arr.length;
    const sumindex = [];
    let marker = length * 2 + 1;
    for(let i = 0; i < length * 2; i++){
        sumindex[i] = marker;
    }
    for(let i = 0; i < arr.length; i++){
        sum += arr[i];
        if (sum >= 0)
            maxslice = i + 1;
        else if (sumindex[sum+length] != marker)
            maxslice = Math.max(maxslice, i - sumindex[sum+length]);
        else
            sumindex[sum+length] = i;
    };
    return maxslice;
};
console.log(longestPositiveSum(arr));

実行結果

5

コードの仕組みを詳しく解説

1. 累積和で部分配列の合計を管理

変数 sum には、配列の先頭から現在の位置 i までの累積和が格納されます。ある区間 [j+1, i] の合計は「位置iまでの累積和 − 位置jまでの累積和」で表せるため、同じ累積和が2回現れた場合、その間の区間の合計は必ず0になります。

2. markerによる初期化チェック

配列 sumindex は、各累積和の値が最初に出現したインデックスを記録するためのものです。累積和は最小で -length になる可能性があるため、sum + length をインデックスとして使用することで、負の値も配列の添字にマッピングしています。

初期値として設定された marker（length * 2 + 1）は、「まだその累積和が出現していないこと」を示す番兵（センチネル値）の役割を果たします。

3. 三つの条件分岐

• sum >= 0 の場合： 先頭からの区間全体で合計が0以上なので、答えの候補は i + 1 となります。
• 同じ累積和が以前に出現している場合： 前回の出現位置との差分 i - sumindex[sum + length] が、合計ちょうど0の部分配列の長さになります。
• 初めて出現する累積和の場合： その位置を sumindex に記録します。

4. 計算量

このアルゴリズムは配列を一度走査するだけなので、時間計算量はO(n)、補助配列のための空間計算量もO(n)です。

まとめ

上記の例では、入力配列 [-1, -1, 0, 1, 1, -1, -1, -1] に対して結果 5 が出力されます。これは、先頭から数えて [0, 1, 1, -1, -1]（または [-1, 0, 1, 1, -1]）といった合計が0以上になる長さ5の部分配列が最長であることを示しています。

累積和とインデックス記録を組み合わせたこの手法は、「特定の条件を満たす最長区間を探す」タイプの問題全般に応用できる強力なパターンですので、ぜひ理解しておきましょう。