Envío 3337

Código

//
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000
#define MOD 1000000007
#define PI 3.14159265
#define EPS 1e-9
#define Pi acos(-1.0)
typedef pair<int, int> ii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define clean(arr,val) memset(arr,val,sizeof(arr))
#define forn(i,n) forr(i,0,n)
#define PB push_back
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vpll;

/*CODE START HERE*/

int n;
ll ans;
vi vec;

// // N^2
// void sol(){
//     ll aux = 0;
//     forn(i,n){
//         aux = 0;
//         forr(j,i,n){
//             aux += vec[j];
//             ans = max(aux,ans); 
//         }
//     }
// }

// n log n
ll solinMiddle(int l, int m, int r){
    ll sumL, sumR, aux;
    sumL = sumR = -INF;
    aux = 0;
    for(int i = m; i >= l; i--){
        aux += vec[i];
        sumL = max(aux,sumL);
    }
    aux = 0;
    for(int i = m+1; i <= r; i++){
        aux += vec[i];
        sumR = max(sumR, aux);
    }
    //cout << "SOL IN MIDDE FOR " << l << " " << m << " " << r << " = " << max(sumR, max(sumL, sumR+sumL)) << "\n";
    return sumR+sumL;
} 

ll sol(int l, int r){
    //cout << "NOW ON " << l << " " << r << "\n";
    if(l == r){
        return vec[l];
    }
    int m = (l+r)/2;
    return max(sol(l,m),max(solinMiddle(l,m,r),sol(m+1,r)));  
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n;
    vec.assign(n,0);
    forn(i,n){
        cin >> vec[i];
    }
    ans = -INF;
    ans = sol(0, n-1); // sol n log n
    cout << ans << "\n";
    return 0;
}