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

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *