fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main()
  5. {
  6.  
  7.     vector<int>a={5,6,-1,4,-6,8,-14,6};
  8.     int n=a.size();
  9.     vector<int>p1(n+1,INT_MIN),p2(n+1,INT_MIN),p3(n+1,INT_MIN),p4(n+1,INT_MIN);
  10.     p1[0]=max(a[0],0);
  11.     p3[0]=p1[0];
  12.     for(int i=1;i<n;i++){
  13.         p1[i]=max({p1[i-1]+a[i],a[i],0});
  14.         p3[i]=max(p3[i-1],p1[i]);
  15.     }
  16.     // for(int i=0;i<n;i++){
  17.     //     cout<<p1[i]<<" ";
  18.     // }
  19.     //     cout<<endl;
  20.     //     for(int i=0;i<n;i++){
  21.     //     cout<<p3[i]<<" ";
  22.     // } 
  23.     p2[n-1]=max({a[n-1],0});
  24.     p4[n-1]=p2[n-1];
  25.     for(int i=n-2;i>=0;i--){
  26.         p2[i]=max({p2[i+1]+a[i],a[i],0});
  27.         p4[i]=max(p4[i+1],p2[i]);
  28.     }
  29.     // cout<<endl;
  30.     //     for(int i=0;i<n;i++){
  31.     //     cout<<p2[i]<<" ";
  32.     // }
  33.     // cout<<endl;
  34.     //     for(int i=0;i<n;i++){
  35.     //     cout<<p4[i]<<" ";
  36.     // }    
  37.  
  38.  
  39.     // for(int i=0;i<n;i++){
  40.  
  41.     //     cout<<i<<" "<<p3[i]<<" "<<p4[i+1]<<endl;
  42.  
  43.     // }
  44.  
  45.     // cout<<endl;
  46.  
  47.     int ans=INT_MIN;
  48.     ans=p4[0];
  49.     // cout<<"---"<<ans<<endl;;
  50.     for(int i=0;i<n;i++){
  51.         ans=max(ans,p3[i]+p4[i+1]);
  52.     }
  53.     cout<<" ans "<<ans<<endl;
  54.     return 0;
  55. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 ans 22
https://ideone.com/lMgLXb
language:
C++ (gcc 8.3)
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!