单调队列:存放一个单调序列。用于对于一个给定大小为k的区间，求出区间内的最值问题。
队列可以双端出队，队列可以看成一半是存放过期的值，一半是存放对未来有用的值。
以a[i]结尾的k窗口内的最大值f[i] = Max{a[i-k+1] ... a[i]};f[i+1] = Max{a[i+1-k+1]... a[i+1]};
所以在求f[i+1]时，可以利用求f[i]时筛选出对f[i+1]有效的值。
在求f[i]时，在区间[i-k+1 + 1,i]内的值才对f[i+1]有效（可以在队列从头开始判断下标来删除一些过期值）。而在这个有效区间内，比a[i]小的数对f[i+1]不是必要的，所以只需要存放a[i]，比a[i]大的数对f[i+1]可能是必要的，就不能删除（通过从队尾开始删除比a[i]小的值)。删除好后的队列存放的是一个从大到小的有效值序列，那f[i]就是队头元素了。
Max Sum of Max-K-sub-sequence
Problem Description
Given
a circle sequence A[1],A[2],A[3]......A[n]. Circle sequence means the
left neighbour of A[1] is A[n] , and the right neighbour of A[n] is
A[1].
Now your job is to calculate the max sum of a
Max-K-sub-sequence. Max-K-sub-sequence means a continuous non-empty
sub-sequence which length not exceed K.
Input
The first line of the input contains an integer T(1<=T<=100) which means the number of test cases.
Then
T lines follow, each line starts with two integers N ,
K(1<=N<=100000 , 1<=K<=N), then N integers followed(all the
integers are between -1000 and 1000).
Output
For
each test case, you should output a line contains three integers, the
Max Sum in the sequence, the start position of the sub-sequence, the end
position of the sub-sequence. If there are more than one result, output
the minimum start position, if still more than one , output the minimum
length of them.
Sample Input
4
6 3
6 -1 2 -6 5 -5
6 4
6 -1 2 -6 5 -5
6 3
-1 2 -6 5 -5 6
6 6
-1 -1 -1 -1 -1 -1
Sample Output
7 1 3
7 1 3
7 6 2
-1 1 1
题意：给定构成圆环的序列和一个k窗口，求(最大的不超过k长度的最大字段和) 且 (子段和长度取长度最小的)。
#include <iostream>
#define maxn 200010
int num[maxn], que[maxn], sum[maxn], ans[maxn];
int main()
{
int t, n, k, m, i, j, a, b, c, p, max, ksum, len;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &k);
m = n;
for (i = 1; i <= n; i++)
{
scanf("%d", &num[i]);
}
for (j = 1; j < k; j++, i++)//构成
n - 1, n, 1, 2, , k - 1
{
num[i] = num[j];
}
n = i;
for (sum[0] = num[0] = 0, i = 1; i < n; i++)
{
sum[i] = sum[i-1] + num[i];
}
a = b = 0;
que[b++] = 0;//开始有个值是0,队列里存放的是有效和sum的下标
for (i = 1; i < n; i++)
{
for (; a < b && que[a] < i - k; a++);//删除过期的值，i-k限定了最大可以取k长度
ans[i] = que[a];//对于i结尾的k窗口，f[i] = sum[i]-sum[que[a]]
for (; a < b && sum[que[b-1]] >= sum[i]; b--);//删除无效值
que[b++] = i;
}
for (i = 1, max = -230000000; i < n; i++)
{
ksum = sum[i] - sum[ans[i]];
if (ksum > max)
{
max = ksum;
p = i;
len = i - ans[i];
}
else if (ksum == max && len > i - ans[i])
{
p = i;
len = i - ans[i];
}
}
c = ans[p] + 1;
if (c > m)
{
c -= m;
}
if (p > m)
{
p -= m;
}
printf("%d %d %d\n", max, c, p);
}
system("pause");
return 0;
}