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