ค่าเฉลี่ยสูงสุดของ Subarray ขนาดอย่างน้อย X และสูงสุด Y ใน C++

โจทย์

ได้รับอาร์เรย์ arr[] และจำนวนเต็มสองจำนวน X และ Y งานคือหา Subarray ที่มีขนาดอย่างน้อย X และสูงสุด Y ซึ่งมีค่าเฉลี่ยสูงสุด

ตัวอย่าง

ถ้าอินพุตอาร์เรย์คือ {2, 10, 15, 7, 8, 4} และ x = 2 และ y = 3 แล้วค่าเฉลี่ยสูงสุดคือ 12.5 ได้จาก

(10 + 15) / 2 = 12.5

อัลกอริทึม

• วนลูปทุก Subarray ที่มีขนาดเริ่มจาก X ถึง Y และหาค่าเฉลี่ยสูงสุด среди ทุก Subarray ดังกล่าว
• เพื่อลดความซับซ้อนด้านเวลา สามารถใช้ Prefix Sum Array เพื่อหาผลรวมของ Subarray ใดๆ ใน O(1)

ตัวอย่างโค้ด

#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