Question:

Given an array of integers, find two non-overlapping subarrays which have the largest sum.
The number in each subarray should be contiguous.
Return the largest sum.

Notice

The subarray should contain at least one number

Answer:

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) {
        // write your code here
        int len = nums.size();
        vector<int> suml(len);
        int cur_max = nums[0];
        int max = cur_max;
        suml[0] = max;
        for (int i = 1; i < len; i++) {
            if (cur_max <= 0) {
                cur_max = nums[i];
            } else {
                cur_max += nums[i];
            }
            if (max < cur_max)
                max = cur_max;
            suml[i] = max;
        }
        vector<int> sumr(len);
        cur_max = nums[len-1];
        max = cur_max;
        sumr[len-1] = max;
        for (int i = len - 2; i >= 0; i--) {
             if (cur_max <= 0) {
                 cur_max = nums[i];
             } else {
                 cur_max += nums[i];
             }
             if (max < cur_max)
                 max = cur_max;
             sumr[i] = max;
        }
        int result = suml[0] + sumr[1];
        for (int i = 1; i < len - 1; i++) {
             int temp = suml[i] + sumr[i+1];
             if (result < temp)
                 result = temp;
        }
        return result;
    }
};