hdu Max Sum of Max-K-sub-sequence 单一队列优化DP

hdu Max Sum of Max-K-sub-sequence 单调队列优化DP

/*求一个环的连续最大子段和。并且输出该最大字段和的和，启示位置和终止位置。
s[i]-s[j]课表示任意最大字段和。当枚举i的时候，只需要求出此时最小的s[j]即可。
此时可以维护一个单调上升的队列。每次取队首元素即可为s[j]的最小值。*/
#include <stdio.h>
#include <cstring>
#define maxn 200001
struct node
{
    int num,id;
    node() {}
    node(int _num,int _id)
    {
        num=_num;
        id=_id;
    }
} q[maxn];
int dp[maxn];
int s[maxn];
int a[maxn];
int main()
{
    int t,n,k;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&k);
        scanf("%d",&a[1]);
        s[1]=a[1];
        for(int i=2; i<=n; i++)
        {
            scanf("%d",&a[i]);
            s[i]=a[i]+s[i-1];
        }
        for(int i=n+1; i<=n+k; i++)
            s[i]=a[i-n]+s[i-1];
        int max=s[1];
        q[0].num=0;
        q[0].id=1;
        int l=1,r=1;
        int head=0,rear=0;
        for(int i=1; i<=n+k; i++)
        {
            while(head<=rear&&q[rear].num>s[i-1]) rear--;
            q[++rear]=node(s[i-1],i);
            while(head<=rear&&i+1-q[head].id>k) head++;
            if(max<s[i]-q[head].num)
            {
                max=s[i]-q[head].num;
                l=q[head].id;
                r=i;
            }
        }
        if(l>n) l=l-n;
        if(r>n) r=r-n;
        printf("%d %d %d\n",max,l,r);
    }
    return 0;
}