Maximum Subarray II

Question

• lintcode: (42) Maximum Subarray II

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.

Example
For given [1, 3, -1, 2, -1, 2],
the two subarrays are [1, 3] and [2, -1, 2] or [1, 3, -1, 2] and [2],
they both have the largest sum 7.

Note
The subarray should contain at least one number

Challenge
Can you do it in time complexity O(n) ?

题解

严格来讲这道题这道题也可以不用动规来做，这里还是采用经典的动规解法。Maximum Subarray 中要求的是数组中最大子数组和，这里是求不相重叠的两个子数组和的和最大值，做过买卖股票系列的题的话这道题就非常容易了，既然我们已经求出了单一子数组的最大和，那么我们使用隔板法将数组一分为二，分别求这两段的最大子数组和，求相加后的最大值即为最终结果。隔板前半部分的最大子数组和很容易求得，但是后半部分难道需要将索引从0开始依次计算吗？NO!!! 我们可以采用从后往前的方式进行遍历，这样时间复杂度就大大降低了。

• reference

class Solution:
    """
    @param nums: A list of integers
    @return: An integer denotes the sum of max two non-overlapping subarrays
    """
    def maxTwoSubArrays(self, nums):
        # write your code here   
        # write your code here   
        n = len(nums)
        a = nums[:]
        aa = nums[:]
        for i in range(1, n):
            a[i] = max(nums[i], a[i-1] + nums[i])
            aa[i] = max(a[i], aa[i-1])
        b = nums[:]
        bb = nums[:]
        for i in range(n-2, -1, -1):
            b[i] = max(b[i+1] + nums[i], nums[i])
            bb[i] = max(b[i], bb[i+1])
        mx = -65535
        for i in range(n - 1):
            mx = max(aa[i]+b[i+1], mx)

        return mx