原題
給定一個(gè)整數(shù)數(shù)組砚嘴，找出兩個(gè)不重疊子數(shù)組使得它們的和最大禾嫉。
每個(gè)子數(shù)組的數(shù)字在數(shù)組中的位置應(yīng)該是連續(xù)的枚粘。
返回最大的和馅闽。
給出數(shù)組[1, 3, -1, 2, -1, 2]，這兩個(gè)子數(shù)組分別為[1, 3]和[2, -1, 2]或者[1, 3, -1, 2]和[2]馍迄，它們的最大和都是7
子數(shù)組最少包含一個(gè)數(shù)
解題思路
- 類似題是[Best Time to Buy and Sell Stock III]
- 找兩個(gè)區(qū)間福也，和最大，則一定存在一個(gè)分割線攀圈，分割線左右兩邊分別轉(zhuǎn)化為求一個(gè)子數(shù)組最大暴凑，即[Maximum Subarray I]
- 從左往右枚舉一遍分割線求出Maximum Subarray，再從右往左枚舉一遍分割線求出Maximum Subarray 這樣時(shí)間復(fù)雜度是O(n)
- 如果從左往右枚舉一次分割線赘来，每次左右分別求maximum Subarray现喳，過程中是有浪費(fèi)的，時(shí)間復(fù)雜度是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):
if not nums:
return 0
size = len(nums)
left, right = [0 for i in range(size)], [0 for i in range(size)]
res, sum, minSum = -sys.maxint - 1, 0, 0
for i in range(size):
sum += nums[i]
res = max(res, sum - minSum)
minSum = min(minSum, sum)
left[i] = res
res, sum, minSum = -sys.maxint - 1, 0, 0
for i in range(size - 1, -1, -1):
sum += nums[i]
res = max(res, sum - minSum)
minSum = min(minSum, sum)
right[i] = res
result = -sys.maxint - 1
for i in range(size - 1):
result = max(result, left[i] + right[i + 1])
return result
