# Time:  O(n)
# Space: O(n)

# Given an array consisting of n integers, find the contiguous subarray
# whose length is greater than or equal to k that 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.
# Note:
# 1 <= k <= n <= 10,000.
# Elements of the given array will be in range [-10,000, 10,000].
# The answer with the calculation error less than 1e-5 will be accepted.
class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        def getDelta(nums, k, avg, accu):
            minval, minval_pos = 2**32, -1
            delta = 0
            for i in xrange(len(nums)):
                accu[i+1] = nums[i] + accu[i] - avg
                if i >= (k-1):
                    if accu[i-k+1] < minval:
                        minval = accu[i-k+1]
                        minval_pos = i-k+1
                    if accu[i+1] - minval >= 0:
                        delta = max(delta, 1.0 * (accu[i+1] - minval) / (i+1 - minval_pos))
            return delta

        accu = [0.0] * (len(nums) + 1)
        left, delta = min(nums), float("inf")
        while delta > 1e-5:
            delta = getDelta(nums, k, left, accu)
            left += delta
        return left

@@ -22,16 +22,17 @@
 : O(n)%0A%0A
+%0A
 # Given 
@@ -94,18 +94,16 @@
 subarray
-%0A#
  whose l
@@ -173,18 +173,16 @@
 e value.
-%0A#
  And you
@@ -580,17 +580,17 @@
 s than 1
-e
+0
 -5 will 
@@ -602,16 +602,17 @@
 cepted.%0A
+%0A
 class So
@@ -788,31 +788,66 @@
 lta(
+avg, 
 nums, k
-, avg, accu):%0A  
+):%0A            accu = %5B0.0%5D * (len(nums) + 1)%0A
     
@@ -856,15 +856,9 @@
     
-minval,
+ 
  min
@@ -871,17 +871,12 @@
 s = 
-2**32, -1
+None
 %0A   
@@ -893,16 +893,18 @@
 elta = 0
+.0
 %0A       
@@ -1046,74 +1046,61 @@
  if 
-accu%5Bi-k+1%5D %3C minval:%0A                        minval = accu%5Bi-k+1%5D
+minval_pos == None or accu%5Bi-k+1%5D %3C accu%5Bminval_pos%5D:
 %0A   
@@ -1174,22 +1174,32 @@
 %5Bi+1%5D - 
+accu%5B
 minval
+_pos%5D
  %3E= 0:%0A 
@@ -1259,22 +1259,32 @@
 %5Bi+1%5D - 
+accu%5B
 minval
+_pos%5D
 ) / (i+1
@@ -1329,47 +1329,8 @@
 ta%0A%0A
-        accu = %5B0.0%5D * (len(nums) + 1)%0A
     
@@ -1432,27 +1432,21 @@
 lta(
+left, 
 nums, k
-, left, accu
 )%0A  

Update maximum-average-subarray-ii.py