We binary search on the answer. Let `P[i] = A[0] + A[1] + ... + A[i-1]`

, the i-th prefix sum under A.

Let's focus our attention on `possible(x)`

, a function that is true iff it is possible to have an average of at least `x`

. Consider the elements `B = [a-x for a in A]`

with corresponding prefix sum `Q[i] = P[i] - i*x`

under B.

We want to know if there is some `>= K`

length subarray in B with average at least zero. Suppose the subarray is `B[i] + B[i+1] + ... + B[j] = Q[j+1] - Q[i]`

. To check whether this quantity is positive, for any `j`

, and any `i <= j - K + 1`

, we should check whether `Q[j+1] >= min_{i <= j-K+1} Q[i]`

. Keeping a running minimum `m`

of this array Q, we can check this in linear time.

Unfortunately, the time constraint on Python solutions is fairly tight, so we need another trick to avoid TLE. If a segment has the biggest average and we break it into two pieces, one of its pieces also has at least the same average. When the length is `>= 2*K`

, we can split it into pieces of at least length `K`

, with the largest such piece being less than length `2*K`

.

Thus, we only need to check segments of length `K <= L < 2*K`

to find an instance of the maximum average. When K is small, this admits an O(NK) solution that we use instead. Our solution in that case is identical to *Maximum Average Subarray I*, repeated K times.

```
def findMaxAverage(self, A, K):
N = len(A)
P = [0]
for x in A:
P.append(P[-1] + x)
if K < 100:
ans = float('-inf')
for k in xrange(K, min(2*K, N+1)):
best_sum = max(P[i+k] - P[i] for i in xrange(N-k+1))
ans = max(ans, best_sum / float(k))
return ans
def possible(x):
m = P[0]
for i, v in enumerate(P):
m = min(m, v-i*x)
if i+K == len(P): break
if P[i+K] - (i+K)*x >= m:
return True
return False
lo, hi = min(A), max(A)
while hi - lo > .00001:
mi = (lo + hi) / 2.0
if possible(mi):
lo = mi
else:
hi = mi
return lo
```