【C++】サイズがX以上Y以下の部分配列の最大平均を求める方法

問題の概要

整数型の配列 arr[] と、2つの整数 X・Y が与えられます。求めるのは、サイズが X 以上 Y 以下となる連続した部分配列の中から、平均値が最大になるものを見つけることです。

例

入力配列が {2, 10, 15, 7, 8, 4}、X = 2、Y = 3 の場合、次のようにして最大平均 12.5 を得ることができます。

(10 + 15) / 2 = 12.5

このケースでは、サイズ2の部分配列 {10, 15} の平均が、条件を満たすすべての部分配列の中で最も高くなります。

アルゴリズム

• X から Y までの各サイズについてすべての部分配列を順に調べ、その中で最大の平均値を求めます。
• 計算量を抑えるために累積和（プレフィックスサム）の配列を利用すると、任意の区間の合計を O(1) で取得できます。

累積和とは、「先頭からその位置までの要素の合計」を事前に計算して格納しておく手法です。これにより、部分配列 arr[i..j] の合計は prefix[j] − prefix[i−1] として即座に求められ、毎回要素を足し合わせる必要がなくなります。

実装例

それでは、実際のC++コードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
double getMaxAverage(int *arr, int n, int x, int y) {
    int prefix[n];
    prefix[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        prefix[i] = prefix[i - 1] + arr[i];
    }
    double maxAverage = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + x - 1; j < i + y && j < n; ++j) {
            double sum = prefix[j];
            if (i > 0) {
                sum = sum - prefix[i - 1];
            }
            double current = sum / double(j - i + 1);
            maxAverage = max(maxAverage, current);
        }
    }
    return maxAverage;
}
int main() {
    int arr[] = {2, 10, 15, 7, 8, 4};
    int x = 2;
    int y = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum average = " << getMaxAverage(arr, n, x, y) << endl;
    return 0;
}

出力

Maximum average = 12.5

コードの解説

まず累積和配列 prefix[] を構築します。外側のループは部分配列の開始位置 i、内側のループは終了位置 j を表し、j は「i + x − 1」から始まることで部分配列のサイズが必ず X 以上になるように制御しています。また、「j < i + y」という条件により、サイズが Y を超えないことも保証されます。各区間の合計を長さで割って平均を計算し、これまでの最大値より大きければ更新していきます。

計算量

時間計算量は O(n × (Y − X + 1)) となります。累積和を使わない場合は区間の合計計算に毎回 O(n) かかるため、この最適化によって大幅な高速化が実現できます。空間計算量は累積和配列の分の O(n) です。