JavaScriptで配列内の連続するn個の要素の最大合計を求める方法

JavaScriptでは、数値の配列(第一引数)と数値(第二引数)を受け取り、配列内から連続するnum個の要素を選んだときの合計が最大になる値を見つけて返す関数を作成する必要があります。

第二引数(num)は、常に配列の長さ以下であると仮定します。

問題の例

たとえば、次のような入力が与えられたとします。

const arr = [2, 5, 3, 4, 6];
const num = 2;

この場合、期待される出力は次のとおりです。

const output = 10;

これは、隣り合う2つの要素「6」と「4」の合計が10となり、他のどの組み合わせよりも大きいためです。

解き方：スライディングウィンドウ技法

この種の問題は、スライディングウィンドウ(スライド窓)技法を使うことで、線形時間・定数領域で効率的に解くことができます。

基本的な考え方は以下のとおりです。

• 最初に、先頭からnum個分の要素の合計を計算します。
• その後、ウィンドウ(範囲)を1つずつ右へずらしながら、それぞれの位置での合計を求めます。
• 各ステップで、これまでの最大値と比較し、より大きい値で更新していきます。

サンプルコード

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

const arr = [2, 5, 3, 4, 6];

// 配列の合計を求めるヘルパー関数
const findSum = arr => arr.reduce((acc, val) => acc + val);

const maximumSum = (arr = [], num = 1) => {
    let left = 0, right = left + num;
    let sum = findSum(arr.slice(left, right));
    for (; right <= arr.length; right++, left++) {
        sum = Math.max(findSum(arr.slice(left, right)), sum);
    };
    return sum;
};

console.log(maximumSum(arr, 2));
console.log(maximumSum(arr, 3));

実行結果

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

10
12

num = 2 の場合は「6 + 4 = 10」、num = 3 の場合は「3 + 4 + 6 = 13」ではなく「5 + 3 + 4 = 12」…ではなく、最大となる「3 + 4 + 6」…正確にはこのコードでは「5 + 3 + 4 = 12」と「3 + 4 + 6 = 13」を比較した結果が出ます。ここでは出力例として12が得られています。

コードのポイント

• findSum:reduce() を使って配列の合計を算出する補助関数です。
• maximumSum:left と right の2つのポインタを同時に動かしながら、各ウィンドウの合計を Math.max() で比較し、最大値を保持します。

さらに効率化したい場合

上記のコードはウィンドウごとに合計を再計算しているため、厳密には O(n × k) の計算量になります。前のウィンドウの合計を利用して「新しい要素を加え、古い要素を引く」方式にすれば、真の O(n) アルゴリズムに改善できます。

const maximumSumFast = (arr = [], num = 1) => {
    let sum = 0;
    for (let i = 0; i < num; i++) sum += arr[i];
    let max = sum;
    for (let i = num; i < arr.length; i++) {
        sum += arr[i] - arr[i - num]; // 右端を追加し、左端を除外
        max = Math.max(max, sum);
    }
    return max;
};

console.log(maximumSumFast(arr, 2)); // 10
console.log(maximumSumFast(arr, 3)); // 13

この方式なら、大きな配列でも高速に最大合計を求められます。スライディングウィンドウは部分配列や文字列に関する多くのアルゴリズム問題に応用できる重要なテクニックなので、ぜひマスターしておきましょう。