Formatted question description: https://leetcode.ca/all/644.html

644. Maximum Average Subarray II

Level

Hard

Description

Given an array consisting of n integers, find the contiguous subarray whose length is greater than or equal to k that has the maximum average value. And you need to output the maximum average value.

Example 1:

Input: [1,12,-5,-6,50,3], k = 4

Output: 12.75

Explanation:

When length is 5, maximum average value is 10.8,

When length is 6, maximum average value is 9.16667.

Thus return 12.75.

Note:

  1. 1 <= k <= n <= 10,000.
  2. Elements of the given array will be in range [-10,000, 10,000].
  3. The answer with the calculation error less than 10-5 will be accepted.

Solution

Use binary search. Initialize min and max to be the minimum element in nums and the maximum element in nums, respectively. Each time calculate mid as the average of min and max, and maintain prevMid which stores the previous value of mid. After mid is calculated, check whether there exists a subarray of nums such that its average value is at least mid. If so, set min = mid. Otherwise, set max = mid. Then calculate the error as the absolute difference between mid and prevMid and set prevMid = mid. The binary search ends when the error does not exceed 10^-5. Finally, return min.

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        final double EPSILON = 0.00001;
        double min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        double prevMid = max;
        double error = Integer.MAX_VALUE;
        while (error > EPSILON) {
            double mid = (min + max) / 2;
            if (exist(nums, mid, k))
                min = mid;
            else
                max = mid;
            error = Math.abs(mid - prevMid);
            prevMid = mid;
        }
        return min;
    }

    public boolean exist(int[] nums, double mid, int k) {
        double sum = 0, prefixSum = 0, minSum = 0;
        for (int i = 0; i < k; i++)
            sum += nums[i] - mid;
        if (sum >= 0)
            return true;
        int length = nums.length;
        for (int i = k; i < length; i++) {
            sum += nums[i] - mid;
            prefixSum += nums[i - k] - mid;
            minSum = Math.min(minSum, prefixSum);
            if (sum >= minSum)
                return true;
        }
        return false;
    }
}

All Problems

All Solutions