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