C++で長さkの部分配列の最大平均を求める方法（スライディングウィンドウ）

この記事では、n個の要素を持つ配列から、指定された長さkの連続する部分配列の中で平均値が最大となるものを見つけ、その最大平均値を返す方法を解説します。

問題の概要

例として、入力が [1,13,-5,-8,48,3]、k = 4 の場合を考えてみましょう。このとき出力は 12.0 になります。これは (13 + (-5) + (-8) + 48) / 4 = 12.0 となるためです。

アルゴリズム：スライディングウィンドウ

この問題は「スライディングウィンドウ（滑動窓）」という手法を使うと効率的に解けます。毎回k個の要素を足し直す代わりに、ウィンドウを1つずらすたびに「新しい要素を加え、古い要素を引く」だけで合計を更新できるのがポイントです。計算量はO(n)に抑えられます。

手順は以下の通りです。

• 最初のk個の要素の合計 sum を計算します。
• maxi := sum として初期値を設定します。
• i を k から配列の末尾まで進めながら、sum := sum + nums[i] − nums[i − k] でウィンドウ内の合計を更新します。
• sum > maxi であれば、maxi := sum と更新します。
• 最後に maxi / k を返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        double maxi = sum;
        for (int i = k; i < nums.size(); i++) {
            sum += nums[i] - nums[i - k];
            if (sum > maxi) {
                maxi = sum;
            }
        }
        return maxi / k;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,13,-5,-8,48,3};
    cout << (ob.findMaxAverage(v, 4));
}

入力例

{1,13,-5,-8,48,3}, 4

出力例

12

計算量について

この実装では、最初のウィンドウの合計計算にO(k)、その後のループは配列の残りの要素に対して1回ずつ処理するだけなので、全体の時間計算量はO(n)、追加のメモリ使用量はO(1)となります。全ての部分配列の平均を総当たりで調べるO(n·k)のアプローチと比べても、非常に効率的な解法です。