fork download 
  1.  
  2. #include <iostream>
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. typedef long long int ll;
  6.  
  7. int main() {
  8.      ll n;
  9.      cin>>n;
  10.      vector<ll>a;
  11.      ll sum =0;
  12.      for(ll i=0;i<n;i++){
  13.          ll y;
  14.          cin>>y;
  15.          sum=sum+y; 
  16.          a.push_back(y*-1);
  17.      }
  18.      // vector<ll>p(n,0); // for s2
  19.      // for(ll i=1;i<=n-3;i++){
  20.      //   p[i]=max(a[i],a[i]+p[i-1]);
  21.      // } 
  22.      vector<ll>s(n,0),smax(n,0);
  23.      s[n-1]=a[n-1];
  24.      smax[n-1]=a[n-1];
  25.      for(ll i=n-2;i>=3;i--){
  26.          s[i]=a[i]+s[i+1];
  27.          smax[i]=max(s[i],smax[i+1]);
  28.      }
  29.       ll temp=-1e18;
  30.       ll curr_sum=0,max_sum=INT_MIN;
  31.       for(ll i=1;i<=n-3;i++){
  32.           curr_sum=max(a[i],a[i]+curr_sum);
  33.           max_sum=max(max_sum,curr_sum);
  34.           ll s2=max_sum;
  35.           ll s4=s[i+2];
  36.           temp=max(temp, s2+s4);
  37.       }
  38.       ll final= sum-2*(-1*temp);
  39.       cout<<final<<endl;
  40.       return 0;
  41. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
7
5 8 -3 2 -1 5 8
stdout 
14
https://ideone.com/Ypmufh
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!