0644. Maximum Average Subarray II

https://leetcode.com/problems/maximum-average-subarray-ii

Description

You are given an integer array nums consisting of n elements, and an integer k.

Find a contiguous subarray whose length is greater than or equal to k that has the maximum average value and return this value. Any answer with a calculation error less than 10-5 will be accepted.

Example 1:

**Input:** nums = [1,12,-5,-6,50,3], k = 4
**Output:** 12.75000
**Explanation:**- When the length is 4, averages are [0.5, 12.75, 10.5] and the maximum average is 12.75
- When the length is 5, averages are [10.4, 10.8] and the maximum average is 10.8
- When the length is 6, averages are [9.16667] and the maximum average is 9.16667
The maximum average is when we choose a subarray of length 4 (i.e., the sub array [12, -5, -6, 50]) which has the max average 12.75, so we return 12.75
Note that we do not consider the subarrays of length < 4.

Example 2:

**Input:** nums = [5], k = 1
**Output:** 5.00000

Constraints:

• n == nums.length

• 1 <= k <= n <= 104

• -104 <= nums[i] <= 104

ac

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double l = Double.MAX_VALUE, r = Double.MIN_VALUE;
        for (int n : nums) {
            l = Math.min(l, n);
            r = Math.max(r, n);
        }

        while (l + 1e-5 < r) {
            double mid = l + (r - l) / 2;
            if (tooSmall(nums, mid, k)) l = mid;
            else r =  mid;
        }

        return l;
    }

    private boolean tooSmall(int[] nums, double mid, int k) {
        // a)add first k element, check if >=0
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i] - mid;
        }
        if (sum >= 0) return true;

        // b)check element after k, track minSum before i-k, if sum-minSum>=0 return true.
        double minSum = 0, prevSum = 0;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - mid;
            prevSum += nums[i-k] - mid;
            minSum = Math.min(minSum, prevSum);

            if (sum - minSum >= 0) return true;
        }

        return false;
    }
}

/*
1) for final maxAvg, sum(nums[i] - maxAvg) must <0, the array make it will be ==0; 2) so use binary search to find maxAvg, for each mid, check if it's tooSmall; 3) a candidate is too small, if some sum(nums[i] - maxAvg) >= 0, thus left = mid increase candidate; 4) in checking, subarray length needs to >k. a)add first k element, check if >=0 b)check element after k, track minSum before i-k, if sum-minSum>=0 return true.
*/