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