返回信息流leetcode 644题目
一般的解法是用二分搜索来猜测最大的平均值，逐渐逼近最终的结果。
但是评论区有人提出了O(N)复杂度的解法
他的代码：
```python
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
```
解释中提到的论文链接：
[ Kai-min Chung, Hsueh-I Lu - An Optimal Algorithm for the Maximum-Density Segment Problem. 2008.](https://arxiv.org/pdf/cs/0311020.pdf)
研究半天没明白，很难受...
求大神解惑
[ema11]
这是一条镜像帖。来源：北邮人论坛 / cpp / #95786同步于 2017/7/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
CPP机器人发帖
【问题】leetcode 644 神奇的O(n)复杂度的解法，没看懂......
intmain
2017/7/17镜像同步7 回复
订阅后，新回复会通过你的通知中心匿名送达。
7 条回复
他构造了一个密度严格单调递减的数组区间（这里的双端队列deque）：例如【1，2，3，4】 => d(1,2) > d(2, 3) > d(3, 4)
大概就是这样。。简单解释一下，没仔细看，不太严谨
当添加一个新的元素[j - k + 1, j]进来，如果它的密度大于队列尾部，那么就融合（pop）：例如【1，2，3，4】 + 5 且 d(4,5) > d(3,4) => 【1，2，3，5】
如果队列头部到新的元素密度高于队列头部密度，那么头部出栈（popleft）：例如【1，2，3，4】 + 5 且 d(1,5) > d(1,2) => 【2，3，4，5】...
【 在 ml3615556 的大作中提到: 】
: 他构造了一个密度严格单调递减的数组区间（这里的双端队列deque）：例如【1，2，3，4】 => d(1,2) > d(2, 3) > d(3, 4)
: 大概就是这样。。简单解释一下，没仔细看，不太严谨
: 当添加一个新的元素[j - k + 1, j]进来，如果它的密度大于队列尾部，那么就融合（pop）：例如【1，2，3，4】 + 5 且 d(4,5) > d(3,4) => 【1，2，3，5】
: ...................
首先谢谢你的回答，我从中也受到一点启发。之后我又回头去啃了啃那个论文，说下我的理解：
问题的目标是找到这样的[i, j]区间，j-i+1 >= k 而且avg(i, j)最大。
算法的整体思路就是枚举区间的右端点j, 对于每个右端点j，找出能够使[i, j]满足长度至少为k而且avg(i, j)最大这一条件，然后再在每个右端点对应的候选解中找出最大的，即是答案。
算法的关键就是找出每个j对应的i, 如果简单的使用枚举的话就是O(n*n)。
对于可能的j来说，对应的i在[0, j-k+1]之间，而且[i,j-k+1]的平均值要尽可能的大，长度要尽可能的小。这样才会使得[i,j]最优(感性上的理解).那么反过来，[0, i]就应该是均值最小，而且长度尽可能的长。
论文中的算法将区间[0, j-k+1]分段，保证每个子段中均值都是递减的(比如[9,4,5,3], 均值分别是9,6.5,6,5.2).这样一来，i必定是某个子段的第一个元素，不可能是字段中其他元素(如果是子段中间某一个元素k，那么选择子段中k后面的元素更优，因为会使得前缀的均值更小！)
这样来看讨论区的代码的话，第一个while循环是为了讲j-k+1添加到[0, j-k+1]区间中，并且更新子段。后一个while循环就是顺序判断子段，选择最优的i了。
至于如果子段对于j不是最优，那么就可以舍弃，在j之后的右端点就不必判断该子段。这一点应该也是可以证明的，详见论文(因为我实在是看不进去了，太数学了......)
有效代码就5行，没必要看论文。。把事情搞复杂了
这个算是一个dp问题
找到状态与状态转移就可以了
你分析得很对，抓住了密度递减子区间对性质（囊括第一个区间为最优），这就够了
【 在 intmain 的大作中提到: 】
:
: 首先谢谢你的回答，我从中也受到一点启发。之后我又回头去啃了啃那个论文，说下我的理解：
: 问题的目标是找到这样的[i, j]区间，j-i+1 >= k 而且avg(i, j)最大。
: ...................
感觉(http://blog.csdn.net/u011542204/article/details/48751763)说的不错，从斜率的角度分析，比较好理解。