题目大意：
给定长度为n的数组，求出最大的区间和，其中区间长度在[1,k]之间
分析：
学动态规划的时候我们会遇到一个经典问题
最大子段和，这个题跟最大子段和很类似 不同的是区间的长度有限制，无法用原算法解决
转换思路
区间[i,j]的和就是ans=sum(j)-sum(i-1) （ j - i <=k）
那么对于每个j 我们肯定希望sum(i-1)最小，所以我们只需要对sum(i-1)维护一个单调队列，然后依次增加 j
同时将单调队列中不满足( j - i <k)的元素出队即可
代码：
#include <iostream>
#include <stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<ctype.h>
using namespace std;
#define maxn 10000010
typedef struct Node
{
int val;
int num;
}node;
typedef struct dqueue
{
node q[maxn];
int l,r;
void ini()
{
l=;
r=;
}
node front()
{
return q[l];
}
node pop()
{
l++;
return q[l-];
}
void push(node x)
{
if(r==l)
{
q[r++]=x;
return;
}
if(x.val<q[l].val)
{
r=l;
q[r++]=x;
return;
}
while(r>=&&(x.val<q[r-].val))
{
r--;
}
q[r++]=x;
}
}Dqueue;
int a[];
int sum[];
Dqueue q;
int main()
{
int n,k,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
sum[]=;
for(int i=;i<=n;i++)
{
scanf("%d",a+i);
}
memcpy(a+n+,a+,n*sizeof(int));
for(int i=;i<=*n;i++)
{
sum[i]=sum[i-]+a[i];
}
node x;
node tmp;
int t=;
q.ini();
int ans=-;
int l,r;
for(int i=;i<=*n;i++)
{
x.val=sum[i-];
x.num=i-;
q.push(x);
while()
{
tmp=q.front();
if(i-tmp.num>k)
{
q.pop();
}
else
{
break;
}
}
if(sum[i]-tmp.val>ans)
{
ans=sum[i]-tmp.val;
l=tmp.num+;
r=i;
continue;
}
}
if(r>n)
{
r-=n;
}
printf("%d %d %d\n",ans,l,r);
}
return ;
}