C++에서 최소 X 및 최대 Y 크기의 하위 배열의 최대 평균

문제 설명

배열 arr[]와 두 개의 정수 X 및 Y가 주어집니다. 작업은 최대 평균을 갖는 최소 X 및 최대 Y 크기의 하위 배열을 찾는 것입니다.

예시

입력 배열이 {2, 10, 15, 7, 8, 4}이고 x =3이고 Y =3이면 다음과 같이 최대 평균 12.5를 얻을 수 있습니다. -

(10 + 15) / 2 = 12.5

알고리즘

• X부터 Y까지 크기의 모든 하위 배열을 반복하고 모든 하위 배열 중에서 최대 평균을 찾습니다.
• 시간 복잡성을 줄이기 위해 접두사 합계 배열을 사용하여 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