42. 最大子数组 II（贪心，隔板）

题目：

给定一个整数数组，找出两个不重叠子数组使得它们的和最大。

每个子数组的数字在数组中的位置应该是连续的。

返回最大的和。

注意：子数组最少包含一个数

样例：

给出数组 [1, 3, -1, 2, -1, 2]

这两个子数组分别为 [1, 3] 和 [2, -1, 2] 或者 [1, 3, -1, 2] 和 [2]，它们的最大和都是 7

Maximum Subarray 中要求的是数组中最大子数组和，这里是求不相重叠的两个子数组和的和最大值，做过买卖股票系列的题的话这道题就非常容易了。动态规划的思想，先从左到右去寻找到i的最大子数组和，将结果存在一个新的数组中；然后再从右到左去寻找最大子数组和；考虑两者之和，取最大值。然后我们使用隔板法将数组一分为二，体现到和数组中，分别求隔开的两部分的和 。

 因为 两个subarray 一定不重叠，所以必定存在一条分割线，分开这两个 subarrays

所以 最后的部分里：

    for(int i = 0; i < n - 1; i++){

           result = max(result, left[i] + right[i + 1]);

        }

        return result;

这里是在枚举 这条分割线的位置

程序：

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 n=nums.size();
        if (n== 0||n==1)
           return 0;
       
        int left[n],right[n];
        int sum=0;
        int sum_max=nums[0];
             
 
        for(int i=0;i<n;i++)
        {
            sum+=nums[i];
            if(sum > sum_max) 
            sum_max = sum;
            if(sum<0)
            sum=0;
            left[i] = sum_max;  //将从左到右遍历所得的各个最大值存left；
        }
         
        sum = 0;
        sum_max = nums[n-1];
        int result =INT_MIN;
 
        for(int i=n-1; i>=0; i--)
        {
            sum +=nums[i];
            if(sum >sum_max) 
             sum_max = sum;
             if(sum<0)
             sum=0;
            right[i]=sum_max;//将从右到左遍历所得的各个最大值存入right;
        }
         for(int i = 0; i < n - 1; i++) 
         result =max(result, left[i] + right[i + 1]);
         //将left与right中最大值比较得到更大值存入result
        return result;
    }
};