Maximum Average Subarray II

Given an array consisting ofnintegers, find the contiguous subarray whoselength is greater than or equal tokthat has the maximum average value. And you need to output the maximum average value.

Example 1:

Input:
 [1,12,-5,-6,50,3], k = 4

Output:
 12.75

Explanation:

when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.

Solution:

Binary Search solution:

time complexity: O( n log m) where m is (10000+10000) * 10^5, which after log2, becomes 30.

Key idea:

Binary search on the element range to find out where the numerical average of the nums array is .

hasAverageAbove function idea:

(nums[i] + nums[i+1] + .... + nums[j]) / (j - i + 1) > x

(nums[i] + nums[i+1] + .... + nums[j]) > x * (j - i + 1)

(nums[i] - x) + (nums[i+1] - x) + .... + (nums[j] - x) > 0 => which is the first step "map" in hasAverageAbove()

curSum stores the sum of the current processing subarray (even though we don't really care and don't need to keep track where the array start and end). Invariant is that curSum is summed by subarray with length longer than or equal to k.

If curSum = sum( nums[ i : j ]), where j - i > k

prevSum = sum( nums[ i : j - k]) because prevSum keeps track of the beginning part of curSum and subtract it out if it's below zero

def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        l, r = -10000, 10000

        while l + 10**-5 < r:
            mid = (l + r) / 2.0
            if self.hasAverageAbove(nums, k, mid):
                l = mid
            else:
                r = mid
        return r

    def hasAverageAbove(self, nums, k, mid):
        tempNums = map(lambda x: x - mid, nums)
        curSum = 0 # stores the sum of contained indices tempNums[i] to tempNums[j]
        prevSum = 0 # stores the sum of i up until j-k, tempNums[i] to tempNums[j-k]
        n = len(tempNums)
        curSum = sum(tempNums[:k])
        if curSum >= 0 : 
            return True

        for i in range(k, n):
            curSum += tempNums[i]
            prevSum += tempNums[i-k]
            if prevSum < 0:
                curSum -= prevSum
                prevSum = 0
            if curSum > 0:
                return True
        return False

Another Solution with O(n) time reference: https://discuss.leetcode.com/topic/96131/python-advanced-o-n-solution-convex-hull-window