I have an array a1, a2, a3, ...., an (n > 0) and integer k (0 < k <= 10^5). Finding optimize the max average subarray with a length of at least k?
Input: 6 2 5 1 7 1 8 2
output 3 5
Explain: [7, 1, 8] is the maximum average subarray that we can have.
I want to know an optimal algorithm for solving that problem.
We can binary search for the largest subarray average in O(n log(range of values)).
On each iteration of binary search, we can check if there is a subarray with average at least mid in linear time. Let pre[r] denote the prefix sum up to index r in the array. The condition we are searching for is equivalent to looking for two indexes l < r such that (pre[r] - pre[l]) / (r - l) >= mid.
Rearranging, this is pre[r] - r * mid >= pre[l] - l * mid. Then, we simply need to compute pre[i] - i * mid for each index while iterating forwards through the array and also maintain the smallest value of that expression encountered from an index at least k before the current index. Once the current value of pre[i] - i * mid is greater than or equal to the minimum so far, we have a subarray with average at least mid and can continue to search in a higher range.