入芽考 maximum subarray應用

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll N = 200000,INF = 1e18;

ll s[N+1] = {},p[N+1] = {};
ll a[N+1] = {},n,sum,best,has_p,mx;
signed main(){
    cin >> n;
    for(int i=0;i<n;i++)cin>>a[i];
    sum = best = has_p = 0, mx = -INF;
    for(int i=0;i<n;i++){
        if(sum+a[i]<0)sum = 0;
        else sum = sum+a[i];
        p[i] = best = max(best,sum);
        if(a[i]>=0)has_p = 1;
        if(!has_p)p[i] = mx = max(mx,a[i]);
    }
    sum = best = has_p = 0, mx = -INF;
    for(int i=n-1;i>=0;i--){
        if(sum+a[i]<0)sum = 0;
        else sum = sum+a[i];
        s[i] = best = max(best,sum);
        if(a[i]>=0)has_p = 1;
        if(!has_p)s[i] = mx = max(mx,a[i]);
    }
    best = -INF;
    for(int i=1;i<n-1;i++)best = max(best,s[i+1]+p[i-1]);
    cout << best << '\n';
}