Trung bình lớn nhất của mảng con có kích thước từ X đến Y trong C++

Đề bài

Cho mảng arr[] và hai số X, Y. Tìm mảng con có kích thước từ X đến Y (inclusive) với trung bình cộng lớn nhất.

Ví dụ: arr = {2,10,15,7,8,4}, X=2, Y=3. Mảng con {10,15} cho trung bình 12.5 (kích thước 2).

Thuật toán

1. Duyệt mọi mảng con có độ dài từ X đến Y.
2. Dùng mảng tiền tố (prefix sum) để tính tổng mảng con trong O(1).
3. Cập nhật trung bình lớn nhất.

Ví dụ minh họa (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 maxAvg = 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 -= prefix[i-1];
            double avg = sum / (j - i + 1);
            maxAvg = max(maxAvg, avg);
        }
    }
    return maxAvg;
}

int main() {
    int arr[] = {2, 10, 15, 7, 8, 4};
    int x = 2, y = 3;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Trung binh lon nhat = " << getMaxAverage(arr, n, x, y) << endl;
    return 0;
}

Kết quả

Trung binh lon nhat = 12.5