2009国家集训队徐持衡的论文《浅谈几类背包问题》里提到的一个经典问题：

长度限制最大连续和问题:

　　给出长度为 n 的序列 X i ,求这个序列中长度不超过 Lmax 的最大连续和。

 

Implementation

 

#include 
     
      using namespace std;const int N(1e5+5);typedef pair
      
        P;P que[N];int main(){    int n, l, ans=0, head=0, tail=0;    scanf("%d%d", &n, &l);    int s=0;    que[tail++]={
   0, s};    for(int i=1, a; i<=n; i++){        scanf("%d", &a);        s+=a;        for(; head!=tail && que[head].first<=i-l; head++);        for(; head!=tail && que[tail-1].second>=s; tail--);        que[tail++]={i, s};        ans=max(ans, s-que[head].second);    }    printf("%d\n", ans);}