This is a binary search solution, should be O(nlog(m)). Still getting time out?

```
def findMaxAverage(self, nums, k):
hi, lo = max(nums), min(nums)
arr = [0.0] * (len(nums) + 1)
def isTrueAvgHigher(avg):
minval = 2**32
for i in xrange(len(nums)):
arr[i+1] = nums[i] + arr[i] - avg
if i >= (k-1):
if arr[i-k+1] < minval:
minval = arr[i-k+1]
if arr[i+1] - minval >= 0:
return True
return False
while (hi - lo) > 1e-5:
mid = 1.0 * (hi + lo) / 2
if isTrueAvgHigher(mid):
lo = mid
else:
hi = mid
return 1.0*(hi+lo)/2
```

#Edit: following is an O(N) solution using similar idea as above, except you directly calculate how much average you need to add to get to the true solution.

```
def findMaxAverage(self, nums, k):
arr = [0.0] * (len(nums) + 1)
def getDelta(avg):
minval, minval_pos = 2**32, -1
delta = 0
for i in xrange(len(nums)):
arr[i+1] = nums[i] + arr[i] - avg
if i >= (k-1):
if arr[i-k+1] < minval: # keep track of lowest average sum .
minval = arr[i-k+1]
minval_pos = i-k+1
if arr[i+1] - minval >= 0: # calculate the diff you need to add to reach the true average.
delta = max(delta, 1.0 * (arr[i+1] - minval) / (i+1 - minval_pos))
return delta
lo = min(nums) # use minimum as initial guess.
for i in range(4): # Should only take 1 iteration, but need at least 4 iterations due to machine precision in calculating average for large arrays.
lo += getDelta(lo)
return lo
```