最大子数组 II

给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。
每个子数组的数字在数组中的位置应该是连续的。
返回最大的和。

 注意事项

子数组最少包含一个数

您在真实的面试中是否遇到过这个题？ Yes
样例
给出数组 [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 length = nums.size();
        vector<int>left(length,0);
        vector<int>right(length,0);
      
        int max = nums[0];
        int temp = nums[0];
        left[0] = nums[0];
        for(int i = 1;i<nums.size();i++) {
            if(temp>=0) {
                if((temp+nums[i]>=0)) {
                temp += nums[i];
            } else {
                temp = 0;
            }
            } else {
                temp = nums[i];
            }
           
            if (temp>=max) {
                    max = temp;
                }
             left[i] = max;
        }
        
        max = nums[length-1];
        temp = nums[length-1];
        right[length-1] = nums[length-1];
        
        for(int i = length-2;i>0;i--){
            if(temp>=0) {
                 if((temp+nums[i]>=0)) {
                temp += nums[i];
               
            }else {
                temp = 0;
            }
            } else {
                temp = nums[i];
            }
           
             if (temp>=max) {
                    max = temp;
                }
             right[i] = max;
        }
       int maxSum = INT_MIN;
       for(int i=0;i<length-1;i++){
           maxSum = (maxSum>(left[i]+right[i+1])?maxSum:(left[i]+right[i+1]));
       }
       return maxSum;
    }
};