JavaScriptで循環配列の最大部分配列和を求める方法

問題

JavaScriptで、整数の配列 arr を唯一の引数として受け取る関数を作成します。

この配列 arr は循環配列として扱います。循環配列とは、配列の末尾の要素の後に先頭の要素が続く構造のことです。私たちのタスクは、arr の空でない部分配列の中から、要素の合計が最大となる値を見つけて返すことです。

入出力の例

入力：

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

出力：

const output = 4;

出力の説明：

この場合、最適な部分配列は [3, -1, 2] です。末尾の -1 の後に先頭の 2 が続くため、3 + (-1) + 2 = 4 となり、これが最大の合計値になります。

アプローチ：Kadaneのアルゴリズムの応用

この問題は、有名なKadaneのアルゴリズムを応用することで効率的に解けます。考え方は、以下の2つのケースを比較するというものです。

• 循環しない場合： 配列の範囲内に収まる通常の部分配列の最大和を、Kadaneのアルゴリズムで求める。
• 循環する場合： 配列の境界をまたぐ部分配列の最大和は、「配列全体の合計 − 最小部分配列和」で求められる。

最終的な答えは、この2つの大きい方です。ただし、配列のすべての要素が負の数である場合は、最小部分配列和が全体の合計と一致してしまうため、単純に最大値（＝負の数の中で絶対値が最も小さい要素）を返す必要があります。

実装例

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

const maxSubarraySumCircular = (arr = []) => {
    let max = arr[0]
    let min = arr[0]
    let currentMax = max
    let currentMin = min
    let sum = arr[0]
    for (let i = 1; i < arr.length; i++) {
        currentMax = arr[i] + Math.max(currentMax, 0)
        max = Math.max(max, currentMax)
        currentMin = arr[i] + Math.min(currentMin, 0)
        min = Math.min(min, currentMin)
        sum += arr[i]
    }
    return max < 0 ? max : Math.max(max, sum - min)
}

console.log(maxSubarraySumCircular(arr));

出力結果

4

この実装では、配列をたった1回のループで走査するだけで、最大部分配列和・最小部分配列和・全体の合計を同時に計算できます。そのため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。