Tìm mảng con trung bình tối đa có độ dài k trong C ++

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

Hãy lấy một ví dụ để hiểu vấn đề,

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

Đầu ra: 10

Giải thích:

Mảng con có kích thước 3 với tổng tối đa là -1, 5, 6 =10

Phương pháp tiếp cận giải pháp

Giải pháp cho vấn đề được thực hiện bằng cách sử dụng mảng bổ trợ để lưu trữ tổng tích lũy cho đến chỉ mục hiện tại trong mảng.

Để tìm tổng các mảng con, chúng ta cần tính toán sự khác biệt giữa các chỉ số của các vị trí của mảng con.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

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

Đầu ra

The maximum average subarray of length 3 begins at index 1