fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int>calculateMaxPrefix(vector<int>&a)
  5. {
  6.     int n= a.size();
  7.     vector<int>prefixMaxSum(n+1,0);
  8.  
  9.     prefixMaxSum[1] = a[0];
  10.  
  11.     for(int i=1; i<=n; i++)
  12.     {
  13.         prefixMaxSum[i]= max({prefixMaxSum[i-1]+a[i-1],a[i-1],0});
  14.     }
  15.  
  16.     return prefixMaxSum;
  17. }
  18.  
  19.  
  20. vector<int>calculateMaxSufix(vector<int>&a)
  21. {
  22.     int n= a.size();
  23.     vector<int>sufixMaxSum(n+1,0);
  24.  
  25.    sufixMaxSum[n] = a[n-1];
  26.  
  27.     for(int i=n-1; i>0; i--)
  28.     {
  29.         sufixMaxSum[i]= max({sufixMaxSum[i+1]+a[i-1],a[i-1],0});
  30.     }
  31.  
  32.     return sufixMaxSum;
  33. }
  34.  
  35. int maxSumTwoNonIntersectingSubArrays(vector<int>&a)
  36. {
  37.     vector<int>prefixMaxSum = calculateMaxPrefix(a);    
  38.     vector<int>sufixMaxSum = calculateMaxSufix(a);
  39.     int n= a.size();
  40.     vector<int>maxSumPrefix(n+1,0);
  41.  
  42.     maxSumPrefix[1] = prefixMaxSum[1];
  43.     int currMax = maxSumPrefix[1];
  44.  
  45.     for(int i=2; i<=n-1; i++)   // because whole array can't be in just prefix we have leave one in the last.
  46.     {
  47.         maxSumPrefix[i] = max(maxSumPrefix[i-1],prefixMaxSum[i]);
  48.     }
  49.  
  50.     vector<int>maxSumSufix(n+1,0);
  51.     maxSumSufix[n]= sufixMaxSum[n];
  52.  
  53.     for(int i=n-1; i>1; i--)
  54.     {
  55.         maxSumSufix[i]= max(maxSumSufix[i+1],sufixMaxSum[i]);
  56.     }
  57.  
  58.  
  59.     int maxSum= 0;
  60.     for(int i=1; i<=n-1; i++)
  61.     {
  62.         maxSum = max(maxSum,maxSumPrefix[i] + maxSumSufix[i+1]);
  63.     }
  64.  
  65.     return maxSum;
  66. }
  67.  
  68. int main() {
  69. 	// your code goes here
  70.    int n;
  71.    cin>>n;
  72.  
  73.    vector<int>a(n,0);
  74.  
  75.    for(int i=0; i<n; i++)
  76.    {
  77.        int input;
  78.        cin>>input;
  79.  
  80.        a[i]= input;
  81.    }
  82.  
  83.     cout<<maxSumTwoNonIntersectingSubArrays(a)<<endl;
  84. }
  85.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
7
2 5 -1 2 -10 1 5
stdout
copy 
14
https://ideone.com/pCCr3I
language:
C++14 (gcc 8.3)
created:
2 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!