题解：P11963 [GESP202503 六级] 环线

· · 题解

解析

在 a_1,\cdots,a_n 组成的环中，选取最大的连续和。

遇到环，就先破环成链，为了减少分类讨论，我们将链复制一条，也就是要 a_{n+i}=a_i，此时问题转化成了，对 r-l+1\le n 时求最大的 a_l+a_{l+1}+\cdots+a_r，首先进行前缀和，令 sum_i=\sum_{l=1}^ia_i，则就是要求 sum_r-sum_{l-1} 的最大值，此时直接枚举 l,r，时间复杂度为 \mathcal{O}\left(n^2\right)，所以要优化。

于是再定义一个数组 b_i 表示在区间 [\max(0,i-n+1),i] 的最小 sum_j 值，这个类似滑动窗口，可以使用单调队列来完成。于是最终答案就是 \max(sum_i-b_{i-1})，时间复杂度为 \mathcal{O}(n)。

代码

注意开long long。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 4e5+1;
ll n, a[N], sum[N], b[N], ans=-2e18;
deque<ll> q;
// b[i]: [i-n+1, i-1]中最小的sum[i]

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i]; a[i+n]=a[i];}
    for(int i=1;i<=n*2;i++) sum[i] = sum[i-1] + a[i];
    for(int i=1;i<=n*2;i++){
        while(!q.empty() && q.front() <= i-n) q.pop_front();
        while(!q.empty() && sum[q.back()] >= sum[i]) q.pop_back();
        q.push_back(i);
        b[i] = sum[q.front()];
    }
    for(int i=1;i<=n*2;i++) ans = max(ans, sum[i] - b[i-1]);
    cout << ans;
}