C++で長さkの最大平均サブ配列を求める方法【累積和によるO(n)実装】

問題概要

この問題では、正と負の値が混在するサイズnの配列 arr[] と整数 k が与えられます。求めるのは、長さkのサブ配列の中で平均が最大になるものです。

なお、要素数が同じであれば「平均が最大のサブ配列」と「合計が最大のサブ配列」は一致するため、この問題は「長さkのサブ配列のうち合計が最大のものを探す」として扱えます。

入出力例

入力：arr[] = {4, -1, 5, 6, -2, 4}、k = 3

出力：10

説明：長さ3のサブ配列のうち合計が最大となるのは {-1, 5, 6} で、その合計は10になります。

解法アプローチ：累積和を活用する

この問題は累積和（prefix sum）を使うことで効率的に解けます。まず、インデックス0から現在位置までの要素の合計を順に格納した補助配列を作成します。

ある区間の合計は、累積和配列の2つの値の差を取るだけで求められます。具体的には、末尾が i である長さkのサブ配列の合計は次のように計算できます。

sumVal = auxSumArray[i] - auxSumArray[i-k]

これにより、すべての長さkのサブ配列の合計を定数時間で求められるため、配列全体を一度走査するだけで答えが得られます。

アルゴリズムの手順

1. 累積和配列 auxSumArray を作成する。
2. 先頭k個の合計を初期の最大値として設定する。
3. インデックスk以降について、直前k個分の合計を計算し、最大値より大きければ更新する。
4. 最大合計となったサブ配列の開始インデックスを返す。

C++での実装例

#include<bits/stdc++.h>
using namespace std;

int findMaxSubArrayAverage(int arr[], int n, int k) {
    if (k > n)
        return -1;

    int *auxSumArray = new int[n];
    auxSumArray[0] = arr[0];
    for (int i=1; i<n; i++)
        auxSumArray[i] = auxSumArray[i-1] + arr[i];

    int maxSum = auxSumArray[k-1], subEndIndex = k-1;

    for (int i=k; i<n; i++) {
        int sumVal = auxSumArray[i] - auxSumArray[i-k];
        if (sumVal > maxSum) {
            maxSum = sumVal;
            subEndIndex = i;
        }
    }

    return subEndIndex - k + 1;
}

int main() {
    int arr[] = {4, -1, 5, 6, -2, 4};
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"The maximum average subarray of length "<<k<<" begins at index "<<findMaxSubArrayAverage(arr, n, k);
    return 0;
}

実行結果

The maximum average subarray of length 3 begins at index 1

このプログラムは、最大平均（＝最大合計）となるサブ配列の開始インデックスを返します。上記の例では、{-1, 5, 6} の開始位置にあたるインデックス1が出力され、対応する合計値は10です。

計算量

• 時間計算量：O(n) ― 配列を一度走査するだけで完了します。
• 空間計算量：O(n) ― 累積和を格納する補助配列が必要です。

補足：スライディングウィンドウならO(1)メモリに削減可能

累積和配列を使わず、現在のウィンドウの合計を変数1つで管理し、右端の要素を加えて左端の要素を引く「スライディングウィンドウ」方式にすれば、追加メモリをO(1)に抑えることもできます。どちらの手法でも計算量はO(n)ですが、実装のシンプルさとメモリ効率のバランスを考慮して選択するとよいでしょう。