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.Notice
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.
的follow up.
上来觉得这题很简单, 既然是求两个不互相交叠的子数组, 并使其和最大. 其实就是枚举划分位, 在每个划分位的左右, 各找到和最大的子数组,这样就是相当于这个划分位的最大和. 而左右两边求数组其实就是 嘛~很简单. 但是这么做的后果是超时TLE.
再仔细分析这种O(n^2)复杂度的做法是否可以优化. 显然在枚举划分位, 并求其左右最大和数组的过程中有相当大的重复性. 我们可以先把划分位左边的最大和子数组,右边最大和子数组求出来先保存, 在O(n)时间先解决这个问题, 之后每次枚举划分位的时候,每个划分位的处理时间都是O(1).总体的时间复杂度就是O(n). 其实还是用DP的思路预先保存避免了子问题的重复解决,代码如下:
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).