Maximum Average Subarray II – Python 3 (Week 14 – 09)

 class Solution:
    """
    @param nums: an array with positive and negative numbers
    @param k: an integer
    @return: the maximum average
    """
    def maxAverage(self, nums, k):
        # write your code here
        start = min(nums)
        end = max(nums)
        n = len(nums)
        
        while end - start >= 0.000001:
            mid = (start + end) / 2
            if self.check(mid, nums, k):
                start = mid
            else:
                end = mid
        return start
        
        
    
    def check(self, mid, nums, k):
        
        n = len(nums)
        
        preSum = [0 for i in range(n+1)]
        minPresum = 0
        for i in range(1, n + 1):
            preSum[i] = preSum[i - 1] + (nums[i - 1] - mid)
            if i >= k:
                minPresum = min(minPresum, preSum[i - k])
            if i >= k and preSum[i] - minPresum >= 0:
                return True
        return False