หาค่าเฉลี่ยสูงสุดของซับอาร์เรย์ความยาว k ใน C++

โจทย์

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

ตัวอย่าง

Input: arr[] = {4, -1, 5, 6, -2, 4}, k = 3

Output: 10

อธิบาย: ซับอาร์เรย์ขนาด 3 ที่มีผลรวมมากที่สุดคือ -1, 5, 6 = 10

แนวทางแก้ปัญหา

ใช้ อาร์เรย์สะสม (Auxiliary Array) เก็บผลรวมสะสมจนถึงดัชนีปัจจุบัน จากนั้นหาผลรวมของซับอาร์เรย์โดยการลบค่าสะสมระหว่างดัชนีปลายทางและดัชนีต้นทาง

โปรแกรมตัวอย่าง

#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