SHARE
TWEET

Untitled

double112233 Jan 27th, 2020 70 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N=1000000+10;
  5. int n,arr[N],ans,l=N,r=-1,mx=-2147483648,lmx[N],rmx[N];
  6. signed main() {
  7.     cin>>n;
  8.     for (int i=0; i<n; i++) {
  9.         cin>>arr[i];
  10.         if (arr[i]>0) {
  11.             ans+=arr[i];
  12.             l=min(l, i);
  13.             r=max(r, i);
  14.         }
  15.     }
  16.     if (!ans) {
  17.         lmx[0]=arr[0];
  18.         for (int i=1; i<n; i++) {
  19.             lmx[i]=max(lmx[i-1], arr[i]);
  20.         }
  21.         rmx[n-1]=arr[n-1];
  22.         for (int i=n-2; i>=0; i--) {
  23.             rmx[i]=max(rmx[i+1], arr[i]);
  24.         }
  25.         for (int i=1; i<n-1; i++) {
  26.             mx=max(lmx[i-1]+rmx[i+1], mx);
  27.         }
  28.         cout<<mx;
  29.         return 0;
  30.     }
  31.     for (int i=l; i<=r; i++) {
  32.         if(arr[i]<=0){
  33.             cout<<ans;
  34.             return 0;
  35.         }
  36.     }
  37.     if(l)
  38.         mx=max(arr[l-1]-arr[l],mx);
  39.     if(r+1<n)
  40.         mx=max(mx,arr[r+1]-arr[r]);
  41.     for (int i=0; i<l-1; i++) {
  42.         mx=max(mx, arr[i]);
  43.     }
  44.     for (int i=r+2; i<n; i++) {
  45.         mx=max(mx, arr[i]);
  46.     }
  47.     for (int i=l+1; i<r; i++) {
  48.         mx=max(mx, 0-arr[i]);
  49.     }
  50.     cout<<ans+mx;
  51. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top