617.py

# 617 Maximum Average Subarray

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
        high = 1 << 32
        low = -high
        EPS = 1e-5
        
        while low + EPS < high:
            mid = (low + high) / 2
#             print(low, mid, high)
            
            # If the average is possible
            if self.check(nums, k, mid):
                low = mid
            else:
                high = mid
        return low
        
    # check if there is a subarray that has average greater or equal to avg
    def check(self, nums, k, avg):
        arr = [0] + [n - avg for n in nums]
        for i in range(1, len(arr)):
            arr[i] += arr[i - 1]
#         print(arr)
        
        low = 0
        high = k
        
        lowmin = arr[0]
        while high < len(arr):
            lowmin = min(arr[low], lowmin)
            if arr[high] >= lowmin:
                return True
            low += 1
            high += 1
        return False