# [LeetCode] 644. Maximum Average Subarray II

## Solution

Since the average must be> = the smallest element in the array, and <= the largest element in the array, we can perform binary search between the smallest and largest elements. Assuming that the AVG is the optimal solution (the largest average), then we cannot find a subarray has greater average than AVG.

Then, turn the problem into a decision problem: Assume AVG is the optimal solution, determine if there is a legal subarray such that the average is greater than AVG. This decision problem equals to determine whether there is a legal subarray so that the sum of the subarray, where each element minus AVG ,are non-negative.

To quickly work out the subarray sum, we can adopt the “prefix sum” algorithm here.

## Code

``````class Solution {
public double findMaxAverage(int[] nums, int k) {
double l = -10001, r = 10001;
while(l + Math.pow(10,-5) < r) {
double mid = (l + r) / 2;
if (check(nums, k, mid)) l = mid;
else r = mid;
}
return r;
}
private boolean check(int[] nums, int k, double avg) {
double[] sum = new double[nums.length+1];
for(int i = 1; i <= nums.length; i++) {
sum[i] = sum[i-1] + nums[i-1] - avg;
}
double min = Double.MAX_VALUE;
for(int i = k; i <= nums.length; i++) {
min = Math.min(min, sum[i - k]);
if (sum[i] - min > 0) return true;
}
return false;
}
}``````