上完题解就走人（不保证题解正确性）

选定以下字段即可查看[color=red]（请各位OIER自我约束！待比赛结束后再查看）[/color]

[color=white]

O(n^2)算法：

设 F(i)为以Ai结尾长度不超过M的最大子序和

对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。

当然这个算法很好写，虽然效率很低。

很显然，这道题可以用堆优化:

用一个二叉堆来维护第i之前的m个前缀和，这样取最小值只要O(1)，每个元素插入一次，删除一次，所以总复杂度是O(nlogn)。

最经典的是用队列优化：（在基于前两个算法上）

用s[i]表示前缀和，把i之前m个s[]组成一个队列。在这m个s[]中，如果i<j，且s[i]>s[j]那么s[i]肯定用不到，因为s[i]比s[j]先出队，s[i]又比s[j]大所以肯定用不到它。所以可以把该队列的元素满足：S1<S2<S3<……<Sk（因为不一定有m个元素，所以用k表示）

这样的话取最小值也是O(1)的，每进一个元素从右边开始比较，如果比它大就删掉（满足刚才的性质），当然加了元素之后还要判断是否队列超过m个元素，超过就把左边的删除。摊还分析一下，每个元素进队一次，出队一次，所以总复杂度是O(n)的。

[/color]

如有缺漏，欢迎指出