lintcode 最大子数组||

给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。
给出数组 [1, 3, -1, 2, -1, 2]
这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7
这道题和上一道题差不多，上一题是找到给定数组的最大子数组。对于这道题，只需要把给定的数组分为两部分，找到左半部分和右半部分的最大子数组的和的最大值即可。因此，对数组进行遍历找到所有可能，找出最大值，而找左右两部分最大值的方法与上一题完全相同：

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 result = nums[0],sum = 0;
        vector<int> left(nums.size(),0),right(nums.size(),0);
        for (int i = 0;i < nums.size();i++) {
            sum += nums[i];
            result = max(result,sum);
            sum = max(sum,0);
            left[i] = result;
        }
        sum = 0,result = nums[nums.size()-1];
        for (int i = nums.size()-1;i > 0;i--) {
            sum += nums[i];
            result = max(result,sum);
            sum = max(sum,0);
            right[i] = result;
        }
        result = INT_MIN;
        for (int i = 0;i < nums.size()-1;i++) {
            result = max(result,left[i] + right[i+1]);
        }
        return result;
    }
};