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.
The subarray should contain at least one number
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.
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 or len(nums) < 2: return 0 n = len(nums) #enumerate the split places """TLE超时的解法 maxall = -sys.maxint for i in xrange(1, n): res1 = nums[0] local = nums[0] for j in xrange(1,i): local = max(local + nums[j], nums[j]) res1 = max(res1, local) local = nums[i] res2 = nums[i] for j in xrange(i+1, n): local = max(local + nums[j], nums[j]) res2 = max(res2, local) maxall = max(maxall, res1 + res2) return maxall """ left = [-sys.maxint-1] * n right = [-sys.maxint-1] * n left[0] = nums[0] local = nums[0] for i in xrange(1, n): local = max(local + nums[i], nums[i]) left[i] = max(left[i-1], local) right[-1] = nums[-1] local = nums[-1] for j in xrange(n-2, -1, -1): local = max(local + nums[j], nums[j]) right[j] = max(right[j+1], local) maxall = -sys.maxint for i in xrange(n-1): maxall = max(maxall, left[i] + right[i+1]) #防止交叠 return maxall
注意题目要求两个子数组不重叠. 所以划分位一定只能包含在一边.一定要注意.
另外其实在从右边往左求划分位右边最大和的过程中,本身已经可以计算最大和了, 这样只需要两次扫描.这种做法在Best Time to Buy and Sell Stock II 中有所体现. 不过相比DP优化而言,这种优化的价值比较小.
时间复杂度O(n), 空间复杂度也为O(n).
原文：http://www.cnblogs.com/sherylwang/p/5635642.html