# 644 maximum average subarray II

```java
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        // the average of any subarray can not be less than min of nums or greater than max of nums
        double lo = min;
        double hi = max;
        double precision = 1e-6;
        // use binary search to find the max average that satisfies the condition
        while (lo + precision < hi) {
            double mid = (lo + hi) / 2;
            if (hasAvg(nums, k, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    // return if there's a subarray with length greater than k and an average greater or equal to target
    private boolean hasAvg(int[] nums, int k, double target) {
        double precision = 1e-6;
        double[] tmp = new double[nums.length];
        double[] prefixes = new double[nums.length];
        // premin要设为0，因为如果window外面的大于0还不如只取window里面的
        double preMin = 0;
        double sum = 0;
        // offset by target so that we can just see if the elements sums up to greater or equal to zero
        for (int i = 0; i < nums.length; i++) {
            tmp[i] = (double)nums[i] - target;
            sum += tmp[i];
            prefixes[i] = sum;
            if (i >= k) {
                // compare it with the minimum element within the elements 
                // before the start of current k length window
                preMin = Math.min(preMin, prefixes[i - k]);
                if (prefixes[i] - preMin >= precision) {
                    return true;
                }
            }
        }
        // because we did not check the window without previous element, this is the last chance
        return prefixes[k - 1] >= precision;
    }
}
```

1. subarray的平均值不会超过array里的min到max的范围，据此来二分查找最大的满足条件的平均值
2. 让所有的元素都减去一个avg就只需要判断和是不是为0就知道原数组平均值是不是为avg
3. 由于subarray是大于等于k长度的，所以我们把window设置为k长度，然后记录winstart左边的prefix sum最小值，用win end处的prefix sum相减就是长度大于（没有等于）k的window的sum最大值，注意preMin初始值要设置为0，这样如果window外的min prefix大于0，我们可以直接取0得到长度等于k的window的sum值，同时这种办法检查不到没有premin的元素，要在最后返回时检查一下
4. 可以看这个[视频](https://www.bilibili.com/video/BV1ct411V7cb/?share_source=copy_web\&vd_source=ebb76e5ea7afd41f05c5788e131128ac)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hzhang.gitbook.io/leetcode-record/binary-search/644-maximum-average-subarray-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.