42 最大子数组Ⅱ

原题网址：https://www.lintcode.com/zh-cn/old/problem/maximum-subarray-ii/#

42. 最大子数组 II

讨论区

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

注意事项

子数组最少包含一个数

您在真实的面试中是否遇到过这个题？

Yes

样例

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

挑战

要求时间复杂度为 O(n)

标签

思路：

对这种求两个数组不重叠区间的问题我是真的非常容易大脑死机，一上来就是确定两个区间的边界，不重叠时 end1 < begin2 --------一把心塞泪，这样走下去当然是想不出解法的。

然后想到一种比较笨的解法，就是遍历nums，每次遍历数组分为左侧部分（0~i）和右侧部分(i+1~n-1)，再分别求左侧部分最大子数组和与右侧部分最大子数组和(又是两个for循环)，如果左右两个最大子数组和大于初始设定的sum（int型的最小值），就更新sum。这样在编译器运行正常，但是提交代码到lintcode上就超出时间限制了。时间复杂度是O（n*n）。

想了下这个方法的主要问题是重复计算，在网上看了别人的答案后恍然大悟，可以用数组将每次的运算结果保存起来，即：

定义两个数组left与right，与nums等长，分别记录每个位置左侧最大子数组和与右侧最大子数组和；

从左往右遍历，计算i左侧部分的最大子数组和left【i】；

再从右往左遍历，计算i右侧部分的最大子数组和right【i】；

遍历left与right，left[k]+right[k+1]表示在第k位拆分数组，得到其子数组的和，找到最大值return出去就可以了。

参考：https://www.cnblogs.com/libaoquan/p/7077870.html

https://blog.csdn.net/qq_23348071/article/details/78698719

https://blog.csdn.net/qq_29726609/article/details/75194105

AC代码：

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
        if (nums.size()==0)
    {
        return 0;
    }
    int n=nums.size();
    vector<int> left(n,0);
    vector<int> right(n,0);
    int maxSum1=nums[0],sum1=0;
    int maxSum2=nums[n-1],sum2=0;
    int i=0,j=n-1;
    for (;i<n;i++)
    {
        sum1+=nums[i];
        if (sum1>maxSum1)
        {
            maxSum1=sum1;
        }
        if (sum1<0)
        {
            sum1=0;
        }
        left[i]=maxSum1;
    }
    
    for (;j>=0;j--)
    {
        sum2+=nums[j];
        if (sum2>maxSum2)
        {
            maxSum2=sum2;
        }
        if (sum2<0)
        {
            sum2=0;
        }
        right[j]=maxSum2;
    }

    int sum=left[0]+right[1];    
    for (int k=1;k<n-1;k++)//k=n-1时left为整个nums的最大子数组和，不符合子数组不重叠要求，且right下标超出范围;
    {
        if (left[k]+right[k+1]>sum)
        {
            sum=left[k]+right[k+1];
        }
    }

    return sum;
    }
};

还可以直接计算 0~k 与 k+1~n-1 部分的最大子数组和，修改代码如下：

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 
        if (nums.size()==0)
    {
        return 0;
    }
    int n=nums.size();
    vector<int> left(n,0);
    vector<int> right(n,0);
    int maxSum1=nums[0],sum1=0;
    int maxSum2=nums[n-1],sum2=0;
    int i=0,j=n-1;
    for (;i<n;i++)//计算0~k的最大子数组和;
    {
        sum1+=nums[i];
        if (sum1>maxSum1)
        {
            maxSum1=sum1;
        }
        if (sum1<0)
        {
            sum1=0;
        }
        left[i]=maxSum1;
    }
    
    for (;j>0;j--)//计算k+1~n-1的最大子数组和;
    {
        sum2+=nums[j];
        if (sum2>maxSum2)
        {
            maxSum2=sum2;
        }
        if (sum2<0)
        {
            sum2=0;
        }
        right[j-1]=maxSum2;
    }

    int sum=left[0]+right[0];    
    for (int k=1;k<n-1;k++)//k=n-1时left为整个nums的最大子数组和，不符合子数组不重叠要求;
    {
        if (left[k]+right[k]>sum)
        {
            sum=left[k]+right[k];
        }
    }

    return sum;
    }
};