切蛋糕

题意： 给定长度为n的序列 给定数m

　 求此序列中长度不大于m的最大区间和 

　 区间元素可能为负

   （洛谷1714）

思路： 区间求和可以想到前缀和

            这里维护一个前缀和单调递增的序列

            若当前元素前缀和大于栈顶元素前缀和 入队

            否则将比当前元素前缀和大的元素全部弹出 再入队

            还需要删除过期的元素（与当前元素的距离已经大于m了）

            再用队尾元素的前缀和减去队首元素的前缀和更新答案 即为最优

code

#include<iostream>
#include<cstdio>
#define M 500010
#define go(i,a,b) for(register int i=a;i<=b;i++)
using namespace std;
int read()
{
  int x=0,y=1; char c; c=getchar();
  while(c<'0'||c>'9') {if(c=='-') y=-1;c=getchar();}
  while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
  return x*y;
}
int a[M],s[M],q[M*4];
int n,m,h,t,ans;
int main()
{
  n=read();m=read(); go(i,1,n) a[i]=read(),s[i]=s[i-1]+a[i];

  go(i,1,n)
    {
      while(s[q[t]]>s[i]&&t>h) t--;
      q[++t]=i;
      while(q[h]<i-m) h++;
      ans=max(ans,s[i]-s[q[h]]);
    }

  printf("%d",ans);
  return 0;
}