> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0644-maximum-average-subarray-ii.md).

# 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

```java
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.
*/
```