80 玄关求调

#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
ll a[200010];
int main(){
    int n;
    std::cin>>n;
    ll s=0;
    for(int i=1;i<=n;i++){
        std::cin>>a[i];
        s+=a[i];
    }
    if(n==2){
        std::cout<<a[1]+a[2];
        return 0;
    }
    std::vector<ll>lm(n+2,-1e18);
    std::vector<ll>rm(n+2,-1e18);
    ll cm=a[1];
    lm[1]=a[1];
    ll me=a[1];
    for(int i=2;i<=n;i++){
        me=std::max(a[i],me+a[i]);
        cm=std::max(cm,me);
        lm[i]=cm;
    }
    cm=a[n];
    rm[n]=a[n];
    me=a[n];
    for(int i=n-1;i>=1;i--){
        me=std::max(a[i],me+a[i]);
        cm=std::max(cm,me);
        rm[i]=cm;
    }
    ll a1=-1e18;
    for(int i=1;i<n;i++)a1=std::max(a1,lm[i]+rm[i+1]);
    std::vector<ll>ln(n+2,1e18);
    std::vector<ll>rn(n+2,1e18);
    ll cn=a[1];
    ln[1]=a[1];
    ll ne=a[1];
    for(int i=2;i<=n;i++){
        ne=std::min(a[i],ne+a[i]);
        cn=std::min(cn,ne);
        ln[i]=cn;
    }
    cn=a[n];
    rn[n]=a[n];
    ne=a[n];
    for(int i=n-1;i>=1;i--){
        ne=std::min(a[i],ne+a[i]);
        cn=std::min(cn,ne);
        rn[i]=cn;
    }
    ll a2=1e18;
    for(int i=1;i<n;i++)a2=std::min(a2,ln[i]+rn[i+1]);
    ll ans=std::max(a1,s-a2);
    std::cout<<ans;
    return 0;
}