#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

ll maxTwoNonOverlappingSubarrays(const vector<ll>& arr) {
    int n = arr.size();
    if (n < 2) return 0;

    vector<ll> leftMax(n);
    vector<ll> rightMax(n);

    // Forward pass: leftMax[i] = max subarray sum in arr[0...i]
    ll currSum = 0;
    ll maxSoFar = -1e18;
    for (int i = 0; i < n; i++) {
        currSum = max(arr[i], currSum + arr[i]);
        maxSoFar = max(maxSoFar, currSum);
        leftMax[i] = maxSoFar;
    }

    // Backward pass: rightMax[i] = max subarray sum in arr[i...n-1]
    currSum = 0;
    maxSoFar = -1e18;
    for (int i = n - 1; i >= 0; i--) {
        currSum = max(arr[i], currSum + arr[i]);
        maxSoFar = max(maxSoFar, currSum);
        rightMax[i] = maxSoFar;
    }

    // Combine maximum sums from left and right partitions
    ll maxTotalSum = -1e18;
    for (int i = 0; i < n - 1; i++) {
        maxTotalSum = max(maxTotalSum, leftMax[i] + rightMax[i + 1]);
    }

    return maxTotalSum;
}

int main() {
    vector<ll> arr = {-10, -5, 2, 4, -15, -20, 1, 2};
    
    // Subarrays [2, 4] (sum 6) and [1, 2] (sum 3) give optimal result 9
    cout << "Max Sum: " << maxTwoNonOverlappingSubarrays(arr) << endl; 
    
    return 0;
}