Maximum average of a subarray of size of at least X and at most Y in C++

Problem statement

Given an array arr[] and two integers X and Y. The task is to find a sub-array of size of at least X and at most Y with the maximum average

Example

If input array is {2, 10, 15, 7, 8, 4} and x = 3 and Y = 3 then we can obtain maximum average 12.5 as follows −

(10 + 15) / 2 = 12.5

Algorithm

• Iterate over every sub-array of size starting from X to size Y and find the maximum average among all such sub-arrays.
• To reduce the time complexity, we can use prefix sum array to get the sum of any sub-array in O(1) complexity

Example

Let us now see an example −

 Live Demo

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

Output

Maximum average = 12.5