翻转 题解

仔细观察一下，发现要求的就是环上两段最大子段和，因为你总是可以通过翻转把这两段拼在一起。

这是一个经典问题（Luogu），直接正反贪心一遍拼在一起，取相反数后再做一次即可。

需要注意的是可能要特判全是负数的情况。

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n,a[N],cnt=0; ll sum=0;

ll f[N],g[N];
ll calc() {
    for (int i=1;i<=n;++i) f[i]=max(f[i-1],0ll)+a[i];
    for (int i=n;i>=1;--i) g[i]=max(g[i+1],0ll)+a[i];
    for (int i=1;i<=n;++i) f[i]=max(f[i-1],f[i]);
    for (int i=n;i>=1;--i) g[i]=max(g[i+1],g[i]);
    ll res=-1e18;
    for (int i=1;i<n;++i) res=max(res,f[i]+g[i+1]);
    return res;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read(),sum+=a[i],cnt+=(a[i]>0);
    if (!cnt) {
        int ans=-1e18;
        for (int i=1;i<=n;++i) ans=max(ans,a[i]);
        printf("%d\n",ans);
        return 0;
    }
    ll ans1=calc();
    for (int i=1;i<=n;++i) a[i]=-a[i];
    ll ans2=calc(); if (!ans2) ans2=-1e18;
    printf("%lld\n",max(ans1,sum+ans2));
    return 0;
}