鸡佬官方题解

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int f[N],g[N],h[N],w[N];
//f[i]正向的时候表示1...i中以a[i]结尾的子序列和
//    反向          i...n中以a[i]结尾的子序列和
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>w[i];
    }
    h[0]=f[0]=-1e9;
    for(int i=1;i<=n;i++) //正向
    {
        f[i]=max(f[i-1],0)+w[i];
        h[i]=max(h[i-1],f[i]);
    }
    g[n+1]=f[n+1]=-1e9; //反向
    for(int i=n;i>=1;i--)
    {
        f[i]=max(f[i+1],0)+w[i];
        g[i]=max(g[i+1],f[i]);
    }
    int res=-1e9;
    for(int i=1;i<=n;i++) //枚举分界点
    {
        
        res=max(res,h[i]+g[i+1]);
    }
    cout<<res<<endl;
    return 0;
}