Let d(x, y) be the density of segment [x, y], ie. `d(x, y) = (A[x]+...+A[y]) / (y-x+1)`

. It can be computed quickly with prefix sums.

Now we refer to section 3 of *Kai-min Chung, Hsueh-I Lu - An Optimal Algorithm for the Maximum-Density Segment Problem. 2008.*

For each ending index j, the current interval for i under consideration, [0, j-K+1] (minus parts on the left we have already discarded), has been decomposed into *minimum* density segments of longest length [hull[i], hull[i+1]-1], and we discard these segments as appropriate. That is, for each i in increasing order, hull[i+1] is the largest index in [hull[i], j-K+1] so that [hull[i], hull[i+1]-1] has minimum density.

This is simply a lower hull of candidate points i, in a geometric interpretation where d(a, b) = the slope of the line segment `(a, P[a]) to (b+1, P[b+1])`

. Then, we can prove that discarding components with lower density than our current candidate d(hull[0], j) must leave us with the highest density option remaining.

```
def findMaxAverage(self, A, K):
N = len(A)
P = [0]
for x in A:
P.append(P[-1] + x)
def d(x, y):
return (P[y+1] - P[x]) / float(y+1-x)
hull = collections.deque()
ans = float('-inf')
for j in xrange(K-1, N):
while len(hull) >= 2 and d(hull[-2], hull[-1]-1) >= d(hull[-2], j-K):
hull.pop()
hull.append(j-K + 1)
while len(hull) >= 2 and d(hull[0], hull[1]-1) <= d(hull[0], j):
hull.popleft()
ans = max(ans, d(hull[0], j))
return ans
```