【题目描述】
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
给定一个整数数组，找出两个 不重叠 子数组使得它们的和最大。每个子数组的数字在数组中的位置应该是连续的。返回最大的和。
注意:子数组最少包含一个数
【题目链接】
http://www.lintcode.com/en/problem/maximum-subarray-ii/
【题目解析】
严格来讲这道题这道题也可以不用动规来做，这里还是采用经典的动规解法。Maximum Subarray 中要求的是数组中最大子数组和，这里是求不相重叠的两个子数组和的和最大值，做过买卖股票系列的题的话这道题就非常容易了，既然我们已经求出了单一子数组的最大和，那么我们使用隔板法将数组一分为二，分别求这两段的最大子数组和，求相加后的最大值即为最终结果。隔板前半部分的最大子数组和很容易求得，但是后半部分难道需要将索引从0开始依次计算吗？NO!!! 我们可以采用从后往前的方式进行遍历，这样时间复杂度就大大降低了。
源码分析:前向搜索和逆向搜索我们使用私有方法实现，可读性更高。注意是求非重叠子数组和，故求maxTwoSub时i 的范围为0, size - 2, 前向数组索引为 i, 后向索引为 i + 1.
复杂度分析:前向和后向搜索求得最大子数组和，时间复杂度 O(2n)=O(n)O(2n)=O(n)O(2n)=O(n), 空间复杂度 O(n)O(n)O(n). 遍历子数组和的数组求最终两个子数组和的最大值，时间复杂度 O(n)O(n)O(n). 故总的时间复杂度为 O(n)O(n)O(n), 空间复杂度 O(n)O(n)O(n).
【参考答案】
http://www.jiuzhang.com/solutions/maximum-subarray-ii/
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
