> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/oj-practices/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/oj-practices/chapter1/binary-search/644-maximum-averagesubarray-ii.md).

# 644     Maximum Average Subarray II

## 644. [Maximum Average Subarray II](https://leetcode.com/problems/maximum-average-subarray-ii/description/)

## 1. Question

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.

## 2. Implementation

**(1) Brute Force**

```java
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int n = nums.length;
        double res = Integer.MIN_VALUE;

        for (int i = 0; i <= n - k; i++) {
            double sum = 0;
            for (int j = i; j < n; j++) {
                sum += nums[j];

                if (j - i + 1 >= k) {
                    res = Math.max(res, sum * 1.0 / (j - i + 1));
                }
            }
        }
        return res;
    }
}
```

**(2) Binary Search**

思路: 这道题要我们找出长度至少为k的最大的subarray 平均数，可以用二分法慢慢地逼近这个最大的subarray 平均数

* 首先我们知道平均数的值一定介于数组中最小数min和最大数max之间, 所以二分搜查的范围是\[min, max]
* 通过观察我们发现，如果一个数是最大的subarray平均数, 记为maxAvg，数组中任意一个subarray上的数减去maxAvg的累积和一定小于等于0， 即(a1 - maxAvg) + (a2 - maxAvg) + (a3 - maxAvg) + ... (an - maxAvg) <= 0.  利用这个性质，我们可以通过一个函数canBeLarger()，判断在二分查找的过程中得到的一个target和我们要找的maxAvg比是大还是小，从而判断搜索的区间
* canBeLarger()的代码第一眼看不太好明白，这里要解释一下代码。我们需要三个变量, sum表示的是subarray\[0, i]与target的差的累积和，preSum表示的是subarray\[0, i - k]与target的差的累积和，minSum代表的是在\[0, i - k]区间里最小的累积和。首先我们的目的是要在数组中**找出长度至少为K的subarray，并且记录subarray上的数与target的差的累积和和0的大小关系。**&#x4E3A;了保证我们找到的subarray的长度至少为K，我们需要通过preSum记录与sum距离为k的subarray累积和。同时通过minSum我们可以知道\[0, i - k]里的累积和中的最小数，如果sum >= minSum, 说明target比我们要找的maxAvg小，返回true。为什么要找\[0, i - k]找到最小的累积和呢，如果最小的累积和与sum相减还是比0大，说明target一定比我们要找的maxAvg要大。

```java
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double start = Integer.MAX_VALUE;
        double end = Integer.MIN_VALUE;

        for (int num : nums) {
            start = Math.min(start, num);
            end = Math.max(end, num);
        }

        while (end - start > 1e-5) {
            double mid = start + (end - start) / 2;

            if (canBeLarger(nums, k, mid)) {
                start = mid;
            }
            else {
                end = mid;
            }
        }
        return start;
    }

    public boolean canBeLarger(int[] nums, int k, double target) {
        double preSum = 0, minSum = 0, sum = 0;

        for (int i = 0; i < k; i++) {
            sum += nums[i] - target;
        }

        if (sum >= 0) {
            return true;
        }

        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - target;
            preSum += nums[i - k] - target;
            minSum = Math.min(minSum, preSum);

            if (sum >= minSum) {
                return true;
            }
        }
        return false;
    }
}
```

## 3. Time & Space Complexity

**Brute Force**: 时间复杂度O(n^2)， 空间复杂度O(1)

**Binary Search:** 时间复杂度O(n \* log(max - min)), 空间复杂度O(1)