class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    int maxTwoSubArrays(vector<int> &nums) {
        int INF = 1000000000;
        int n = nums.size();
        int v[n + 2], sp[n + 2], mx1[n + 2], mx2[n + 2], ans = -INF;
        v[0] = v[n + 1] = sp[0] = 0;
        mx1[0] = mx2[n + 1] = -INF;

        for (int i = 1; i <= n; i++)
            v[i] = nums[i - 1];
        for (int i = 1; i <= n; i++)
            sp[i] = sp[i - 1] + v[i];

        int mn = 0, mx = sp[1];
        for (int i = 1; i <= n; i++){
            if (mx < sp[i] - mn)
            mx = sp[i] - mn;
            if (mn > sp[i])
            mn = sp[i];
            mx1[i] = mx;
        }
        mn = 0, mx = sp[n] - sp[n - 1];
        for (int i = n; i > 0; i--){
            if (mx < sp[n] - sp[i - 1] - mn)
            mx = sp[n] - sp[i - 1] - mn;
            if (mn > sp[n] - sp[i - 1])
            mn = sp[n] - sp[i - 1];
            mx2[i] = mx;
        }
        for (int i = 1; i < n; i++)
            ans = max(ans, mx1[i] + mx2[i + 1]);
        return ans;
    }
};