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.

Solution

两个范围内数组相加的最大值。

if the question is about two range then consider two pointers.

don't give total defualt value 0

don't do p1[i] + p2[i] due to the overlapping issue.

for i in range\(n - 1\):

    total = max\(total, p1\[i\] + p2\[i + 1\]\) no overlapping issue.

return total

class Solution:
    """
    @param nums: A list of integers
    @return: An integer denotes the sum of max two non-overlapping subarrays
    two pointers.
    """
    #两个范围内数组相加的最大值。
    def maxTwoSubArrays(self, nums):
        # write your code here    
        n = len(nums)

        result = sys.maxint * -1

        p1 = [0] * n
        p2 = [0] * n 

        total, sum = sys.maxint * -1, 0

        for i in range(n):
            sum += nums[i]
            total = max(total, sum)
            p1[i] = total
            sum = max(sum, 0)

        total, sum = sys.maxint * -1, 0
        for i in range(n - 1, -1, -1):
            sum += nums[i]
            total = max(total, sum)
            p2[i] = total
            sum = max(sum, 0)

        for i in range(n - 1):
            result = max(result, p1[i] + p2[i + 1])

        return result