环形区间连续和问题[长度不超过n的连续最大和]

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
int Case = 1;
ll cc[maxn], pre[maxn];
void solve() {
    int n, m;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
    	scanf("%lld", &cc[i]);
    	cc[i+n] = cc[i];
    }
    for(int i = 1; i <= 2*n; i++) {
    	pre[i] = pre[i-1] + cc[i];
    }
    list<int>q;
    ll res = 0;
    q.push_front(0);
    for(int i = 1; i <= 2*n; i++) {
    	while(!q.empty() && pre[q.front()] > pre[i]) q.pop_front();
    	q.push_front(i);
    	while(!q.empty() && i-q.back() > n) q.pop_back();
    	res = max(res, pre[i]-pre[q.back()]);
    }
    printf("%lld\n", res);
    return;
}

int main() {
    while(Case--) {
        solve();
    }
    return 0;
}