蒜厂年会|2019 蓝桥杯省赛 B 组模拟赛(一)第10题

原题链接 https://nanti.jisuanke.com/t/36118
将环队列变成链式队列，再统计长度最大为n的区间中的和最大

#include<iostream>
#include<deque>
using namespace std;
typedef long long ll;
int cp[200001];
ll sum[200001];
int main(){
    int n;
    cin>>n;
    for(int i = 1; i <= n ;i++){
        cin>>cp[i];
        cp[i + n] = cp[i]; //将环队列变成链式队列
    }
    for(int i = 1; i <= 2 * n; i++){ // 类似于数学中的前n项和的求法
        sum[i] = sum[i - 1] + cp[i];
    }
    deque<int > que; //双向队列 对头保存i前面的sum最小的下标值
    que.push_back(0);
    ll ans = cp[1];
    for(int i = 1; i <= 2 * n; i++){
        if(!que.empty() && que.front() < i - n){
            que.pop_front();
        }
        ans = max(ans , sum[i] - sum[que.front()]);
        while (!que.empty() && sum[que.back()] >= sum[i]) { //维护一个单调队列
            que.pop_back();
        }
        que.push_back(i);
    }
    cout<<ans;
    return 0 ;
}