求小于等于k长度的最大区间和

题意

给出一个序列，求长度小于等于k的最大区间和并输出起点和终点
1<=n<=100000
1<=k<=n
 
题解：先算出前缀和,利用单调队列的性质，在单调队列中存储sum[] 的下标，并保持队列中的前缀和是保持递增的。
类似题 hdu3415

#include<stdio.h>
#include<iostream>
using namespace std;
#define de(x) cout<<#x<<" = "<<x<<endl
const int N  = 100010;
const int inf = 100000010;
int que[N],sum[N];
int main()
{
    int n,k,a,i,ans,ans1,ans2;
    int front,tail;
    scanf("%d%d",&n,&k);
    sum[0]=0;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        sum[i]=sum[i-1]+a;
    }
    front = 0;tail = 0;
    ans=-inf;
    for(i=1;i<=n;i++)
    {
        while(tail>front&&sum[i-1]<sum[que[tail-1]])
            tail--;
        que[tail++]=i-1;
        while(tail>front&&i-que[front]>k)
            front++;
        if(ans<sum[i]-sum[que[front]])
        {
            ans=sum[i]-sum[que[front]];
            ans1=que[front]+1;
            ans2=i;
        }
    }
    printf("%d %d %d",ans,ans1,ans2);
}