Maximum Contigous Array

#include<bits/stdc++.h>
using namespace std;

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;

//MaximumContigousSubarray


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

   /* ll dp[n];
    dp[0] = a[0];
    for(int i = 1 ; i < n ; i++ ){
      dp[i] = max(dp[i-1] + a[i] , a[i]);
    }

    cout << *max_element(dp , dp + n);*/
    //Space Complexity O(n)

    ll ans = a[0];

    ll prevmax = 0;
    int prevind = 0 , currind = 0 ;
    for(int i = 0 ; i < n ; i++ ){
     /* if(ans < max(a[i] , a[i] + prevmax)){

        if(prevmax + a[i] >= a[i]){
          currind = i;
        }
        else{
          prevind = currind = i;
        }

      }*/

        ans = max({ans ,a[i] , a[i] + prevmax});
        prevmax = max(a[i] , prevmax + a[i]);
      }
    //}
    //cout << prevind << " " << currind << "\n";
    cout << ans;
    //Printing indexes also
    //Space complexity O(1);























    return 0;

}