fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6. using ll = long long;
  7.  
  8. ll maxTwoNonOverlappingSubarrays(const vector<ll>& arr) {
  9.     int n = arr.size();
  10.     if (n < 2) return 0;
  11.  
  12.     vector<ll> leftMax(n);
  13.     vector<ll> rightMax(n);
  14.  
  15.     // Forward pass: leftMax[i] = max subarray sum in arr[0...i]
  16.     ll currSum = 0;
  17.     ll maxSoFar = -1e18;
  18.     for (int i = 0; i < n; i++) {
  19.         currSum = max(arr[i], currSum + arr[i]);
  20.         maxSoFar = max(maxSoFar, currSum);
  21.         leftMax[i] = maxSoFar;
  22.     }
  23.  
  24.     // Backward pass: rightMax[i] = max subarray sum in arr[i...n-1]
  25.     currSum = 0;
  26.     maxSoFar = -1e18;
  27.     for (int i = n - 1; i >= 0; i--) {
  28.         currSum = max(arr[i], currSum + arr[i]);
  29.         maxSoFar = max(maxSoFar, currSum);
  30.         rightMax[i] = maxSoFar;
  31.     }
  32.  
  33.     // Combine maximum sums from left and right partitions
  34.     ll maxTotalSum = -1e18;
  35.     for (int i = 0; i < n - 1; i++) {
  36.         maxTotalSum = max(maxTotalSum, leftMax[i] + rightMax[i + 1]);
  37.     }
  38.  
  39.     return maxTotalSum;
  40. }
  41.  
  42. int main() {
  43.     vector<ll> arr = {-10, -5, 2, 4, -15, -20, 1, 2};
  44.  
  45.     // Subarrays [2, 4] (sum 6) and [1, 2] (sum 3) give optimal result 9
  46.     cout << "Max Sum: " << maxTwoNonOverlappingSubarrays(arr) << endl; 
  47.  
  48.     return 0;
  49. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max Sum: 9
https://ideone.com/ZPEm3n
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!