> For the complete documentation index, see [llms.txt](https://longxingtan.gitbook.io/mle-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://longxingtan.gitbook.io/mle-interview/01_leetcode/00_binary_search/644.-maximum-average-subarray-ii.md).

# \*644. Maximum Average Subarray II

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

## solution

```python
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        l = min(nums)
        r = max(nums)

        while l < r:
            mid = l + (r - l) // 2
            if self.check(nums, mid, k):
                l = mid
            else:
                r = mid
        return l

    def check(self, nums, mid, k):
        # Returns True if there's a subarray, where its length >= k and its average sum >= m
        summ = 0
        prev_sum = 0
        min_prev_sum = 0
        for i, num in enumerate(nums):
            summ += num - mid
            if i >= k:
                prev_sum += nums[i - k] - mid
                min_prev_sum = min(min_prev_sum, prev_sum)
            if i + 1 >= k and summ >= min_prev_sum:
                return True
        return False
```

时间复杂度：O()\
空间复杂度：O()