C++에서 k 길이의 최대 평균 하위 배열 찾기

이 문제에서는 양수 값과 음수 값과 정수 k로 구성된 크기 n의 배열 arr[]이 제공됩니다. 우리의 임무는 k 길이의 최대 평균 하위 배열을 찾는 것입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

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

출력: 10

설명:

최대 합이 -1, 5, 6 =10인 크기 3의 하위 배열

솔루션 접근 방식

문제에 대한 해결책은 보조 배열 을 사용하여 수행됩니다. 배열의 현재 인덱스까지 누적 합계를 저장합니다.

하위 배열의 합을 찾으려면 하위 배열의 위치 인덱스 간의 차이를 계산해야 합니다.

우리 솔루션의 작동을 설명하는 프로그램,

예시

#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