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)`

is 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
```