学步园

给出一个数环，求最大子段和。

扩展数环为两倍，相当于求固定长度为n的子段和。

保证队列内部元素为单增且距离不超过n，最优解必然是队尾减去队首。

比赛的时候不知道为啥wa成狗了。。大概是忘记把数组开成两倍大小了吧。。

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
#define MAXN 1000010
#define max(a, b) ((a) > (b) ? (a) : (b))
#define suc(x, k) (((x) > (k)) ? ((x) - (k)) : (x))

int c[MAXN], sum[MAXN << 1], que[MAXN << 1];
int ans;
int main()
{
//    freopen("E.in", "r", stdin);

    int cas; scanf("%d", &cas);
    while(cas--)
    {
        int n; scanf("%d", &n);
        sum[0] = 0;

        for(int i = 1; i <= n; i++) scanf("%d", c + i);
        for(int i = 1; i <= 2 * n; i++) sum[i] = sum[i - 1] + c[suc(i, n)];

        int h = 0, t = -1;
        ans = 0;
        for(int i = 0; i <= 2 * n; i++)
        {
            while(t >= h && sum[i] < sum[que[t]]) ans = max(ans, sum[que[t]] - sum[que[h]]), t--;
            while(t >= h && i - que[h] > n) ans = max(ans, sum[que[t]] - sum[que[h]]), h++;
            que[++t] = i;
        }
        ans = max(ans, sum[que[t]] - sum[que[h]]);
        printf("%d\n", ans);
    }
    return 0;
}