0-1 Hole Kdane Algorithm Solution and Code

You are given an array of N integers. You select all possible contagious subarrays. For each possible subarray, you are allowed to choose at most one of the integers and remove it. Out of all such possibilities, you need to find out a selection of a contagious subarray and the choice of removing one integer which results in the maximum possible sum.

Please note, that you can also choose, not to remove any integer.

Input

The first line will contain an integer N, the number of integers in a given Array.
The second line will contain N integers of the given Array separated by space

Constraints

1 ≤ N ≤ 105
-104 ≤ Each Value in Array ≤ 104

Output

Output a single integer, denoting the maximum possible sum as described in the question.

Example

Input

6
1 2 3 -100 3 2

Output

Input

6
-1 -2 -3 -4 -5 -6

Output

-1

The solution to the above question is


#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {

int n;cin>>n;
vi v(n);

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

vi fwd(n),bwd(n);

int currmax=v[0],maxsofar=v[0];
fwd[0]=v[0];
for(int i=1; i<n; i++){
    currmax=max(currmax+v[i],v[i]);
    maxsofar=max(currmax,maxsofar);
    fwd[i]=currmax;
}

currmax=maxsofar=bwd[n-1]=v[n-1];

for(int i=n-2; i>=0; i--){
    currmax=max(v[i],currmax+v[i]);
    maxsofar=max(maxsofar,currmax);
    bwd[i]=currmax;
}

int maxElem=maxsofar;

for(int i=1; i<n-1; i++){
    int curr=max(0LL,fwd[i-1]+bwd[i+1]);
    maxElem=max(maxElem,curr);
}
if(maxElem==0)cout<<*max_element(v.begin(),v.end());
else cout<<maxElem;




}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
//   cin >> t;
  while (t--) solve();



  return 0;
}