Tìm trung bình cộng lớn nhất của mảng con độ dài k trong C++

Trong bài toán này, cho mảng arr[] kích thước n chứa giá trị dương và âm cùng một số nguyên k. Nhiệm vụ là tìm mảng con độ dài k có trung bình cộng lớn nhất.

Ví dụ minh họa:

Đầu vào: arr[] = {4, -1, 5, 6, -2, 4}, k = 3

Đầu ra: 10

Giải thích:

Mảng con kích thước 3 có tổng lớn nhất là -1, 5, 6 = 10

Phương pháp giải quyết

Giải pháp sử dụng mảng phụ lưu trữ tổng tích lũy đến chỉ mục hiện tại.

Để tìm tổng các mảng con, ta tính hiệu giữa các chỉ mục vị trí của mảng con.

Chương trình minh họa

Ví dụ

#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;
}

Kết quả

The maximum average subarray of length 3 begins at index 1