单调队列:存放一个单调序列。用于对于一个给定大小为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;
}