單調(diào)隊(duì)列:存放一個(gè)單調(diào)序列。用于對(duì)于一個(gè)給定大小為k的區(qū)間，求出區(qū)間內(nèi)的最值問題。

隊(duì)列可以雙端出隊(duì)，隊(duì)列可以看成一半是存放過期的值，一半是存放對(duì)未來有用的值。

以a[i]結(jié)尾的k窗口內(nèi)的最大值f[i] = Max{a[i-k+1] ... a[i]};f[i+1] = Max{a[i+1-k+1]... a[i+1]};

所以在求f[i+1]時(shí)，可以利用求f[i]時(shí)篩選出對(duì)f[i+1]有效的值。

在求f[i]時(shí)，在區(qū)間[i-k+1 + 1,i]內(nèi)的值才對(duì)f[i+1]有效（可以在隊(duì)列從頭開始判斷下標(biāo)來刪除一些過期值）。而在這個(gè)有效區(qū)間內(nèi)，比a[i]小的數(shù)對(duì)f[i+1]不是必要的，所以只需要存放a[i]，比a[i]大的數(shù)對(duì)f[i+1]可能是必要的，就不能刪除（通過從隊(duì)尾開始刪除比a[i]小的值)。刪除好后的隊(duì)列存放的是一個(gè)從大到小的有效值序列，那f[i]就是隊(duì)頭元素了。

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
題意：給定構(gòu)成圓環(huán)的序列和一個(gè)k窗口，求(最大的不超過k長(zhǎng)度的最大字段和) 且 (子段和長(zhǎng)度取長(zhǎng)度最小的)。


#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++)//構(gòu)成 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;//開始有個(gè)值是0,隊(duì)列里存放的是有效和sum的下標(biāo) 
        for (i = 1; i < n; i++)
        {
            for (; a < b && que[a] < i - k; a++);//刪除過期的值，i-k限定了最大可以取k長(zhǎng)度 
            ans[i] = que[a];//對(duì)于i結(jié)尾的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;
}