Maximum Subarray II

Question

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) ?

Analysis

• 空
• 一个number

注意点

• non-overlapping

Thoughts

这一题有点像buy stock III, 分割两边然后再求最大值的做法，所以采取类似的做法

如果采取maximum subarray的办法去求每一个index的两边，则需要 O(n^2)

这里才去和buy stock III类似的题目，但是略有不同 对于左边，用两个array left[]和leftMax[] left[i]表示以i为end的subarray的maximum sum leftMax[i]表示在[0:i]区间内的subarray的maximum sum （不一定以nums[i]为end）

右边同理，剩下的同buy stock iii

Solution

O(n^2)做法

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    
        if not nums:
            return 0

        length = len(nums)    

        left = [0 for i in range(length)]    
        right = [0 for i in range(length)]   

        #at least one number, so stop at the last 2th element
        #left part include current element
        for i in range(length-1):
            leftPart = nums[:i+1]
            rightPart = nums[i+1:]
            left[i] = self.maxSubArray(leftPart)
            right[i] = self.maxSubArray(rightPart)

        #start calcuate for each index
        maxSum = sys.maxint * -1
        for i in range(length-1):
            currentSum = left[i] + right[i]
            if currentSum > maxSum:
                maxSum = currentSum
        return maxSum

    def maxSubArray(self, nums):
        # write your code here
        if not nums:
            return 0
        currentSum = nums[0]
        length = len(nums)
        if length == 1:
            return nums[0]
        maxSum = sys.maxint * -1
        for i in range(1, length):
            if currentSum < 0:
                currentSum = nums[i]
            else:
                currentSum += nums[i]
            if maxSum < currentSum:
                maxSum = currentSum
        return maxSum

O(n)做法

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    
        if not nums:
            return 0

        length = len(nums)

        left = [0 for i in range(length)]
        leftMax = [ 0 for i in range(length)]
        right = [0 for i in range(length)]
        rightMax = [ 0 for i in range(length)]

        left[0] = nums[0]
        leftMax[0] = nums[0]
        for i in range(1, length):
            if left[i-1] < 0:
                left[i] = nums[i]
            else:
                left[i] = left[i-1] + nums[i]
            leftMax[i] = max(left[i], leftMax[i-1])

        right[length-1] = sys.maxint * -1
        rightMax[length-1] = sys.maxint * -1

        for i in range(length-2, -1, -1):
            if right[i+1] < 0:
                right[i] = nums[i+1]
            else:
                right[i] = right[i+1] + nums[i+1]
            rightMax[i] = max(right[i], rightMax[i+1])

        #start calcuate for each index
        maxSum = sys.maxint * -1
        for i in range(length-1):
            currentSum = leftMax[i] + rightMax[i]
            if currentSum > maxSum:
                maxSum = currentSum
        return maxSum