Problem 2

#include <bits/stdc++.h>

using namespace std;
#define int long long

signed main() {
    int n;
    cin>>n;

    vector<int> a(n),pref(n+1,0),suf(n+1,0), max_suf(n+1,0);
    int mn=0,ans=0;

    for(int i=0;i<n;i++){
        cin>>a[i];

        pref[i+1]=pref[i]+a[i];
        ans=max(ans,pref[i+1]-mn);
        mn=min(mn,pref[i+1]);
    }

    for(int i=(int)a.size()-1;i>=0;i--){
        suf[i]=suf[i+1]+a[i];
        max_suf[i]=max(max_suf[i+1],suf[i+1]+a[i]);
    }

    int mx=0;
    for(int i=0;i<a.size();i++){
        mx=max(mn,pref[i]);
        ans=max(ans,pref[i]+max_suf[i+1]);
    }

    cout<<ans;
}