JavaScriptで特定の長さを持つ部分配列の最大平均値を求める方法

問題概要

整数の配列 arr を第1引数に、数値 num を第2引数として受け取るJavaScript関数を作成する必要があります。

この関数の目的は、長さがちょうど num である連続する部分配列（サブアレイ）の中から、平均値が最大となるものを見つけ出し、その最大平均値を出力することです。

入力例

const arr = [1, 12, -5, -6, 50, 3];
const num = 4;

出力例

const output = 12.75;

出力の解説

このケースでは、求めるべき部分配列は [12, -5, -6, 50] です。これら4つの要素の合計は 51 となり、51 ÷ 4 = 12.75 が最大平均値になります。

解決のアプローチ：スライディングウィンドウ法

この問題を効率的に解くには、「スライディングウィンドウ（滑動窓）」という手法が非常に有効です。

すべての部分配列について毎回合計を再計算すると非効率ですが、隣接するウィンドウ同士はほとんどの要素を共有しているため、右端に新しい要素を加え、左端から外れた要素を引くだけで次の合計を求められます。これにより、全体の計算量を O(n) に抑えることができます。

コード例

const arr = [1, 12, -5, -6, 50, 3];
const num = 4;

const maxAverage = (arr = [], num) => {
    // 最初のウィンドウ（先頭からnum個）の合計を計算
    let sum = arr.slice(0, num).reduce((acc, v) => acc + v, 0);
    let max = sum;

    // ウィンドウを1つずつ右へスライド
    for (let i = 1; i <= arr.length - num; i++) {
        sum = sum + arr[i + num - 1] - arr[i - 1];
        max = Math.max(max, sum);
    }

    // 合計を要素数で割って平均値を返す
    return max / num;
};

console.log(maxAverage(arr, num));

実行結果

12.75

コードのポイント解説

・まず reduce() メソッドを使い、配列の先頭から num 個分の要素の合計を初期値として sum に設定します。
・続く for ループでは、ウィンドウを1つずつ右へ移動させます。各ステップで、新しくウィンドウに入る要素 arr[i + num - 1] を加算し、外れる要素 arr[i - 1] を減算することで、合計を定数時間で更新しています。
・Math.max() によってこれまでの最大合計を常に追跡し、ループ終了後に最大合計を num で割ることで、目的の最大平均値が得られます。

この手法を使えば、要素数が多い配列でも高速に処理できるため、実際の開発現場やコーディング面接においても役立つテクニックです。