fork download
copy 
  1. // 2 max sum subarray that don't intersect each other
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. main(){
  6.     int n,mx=0;
  7.     cin>>n;
  8.     vector<int>v(n),pref(n),suff(n);
  9.     for(auto &it:v)cin>>it;
  10.     pref[0]=max(0,v[0]);
  11.     suff[n-1]=max(0,v[n-1]);
  12.  
  13.     for(int i=1;i<n;i++){
  14.         pref[i]=max(v[i],max(pref[i-1]+v[i],0));
  15.     }
  16.  
  17.     for(int i=n-2;i>=0;i--){
  18.         suff[i]=max(v[i],max(0,v[i]+suff[i+1]));
  19.     }
  20.  
  21.     vector<int>prefixmaxsum(n,0);
  22.     prefixmaxsum[0]=pref[0];
  23.     for(int i=1;i<n;i++)prefixmaxsum[i]=max(prefixmaxsum[i-1],pref[i]);
  24.  
  25.     vector<int>suffixmaxsum(n,0);
  26.     suffixmaxsum[n-1]=suff[n-1];
  27.     for(int i=n-2;i>=0;i--)suffixmaxsum[i]=max(suffixmaxsum[i+1],suff[i]);
  28.  
  29.     for(int i=0;i<n-1;i++){
  30.         mx=max(mx,prefixmaxsum[i]+suffixmaxsum[i+1]);
  31.     }
  32.  
  33.    cout<<max(mx,prefixmaxsum[n-1])<<"\n";
  34. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
7
1 5 -7 -8 -7 5 1
stdout
copy 
12
https://ideone.com/jvK1bT
language:
C++14 (gcc 8.3)
created:
9 days 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!