Maximum Subarray II · 數據結構與算法/leetcode/lintcode題解

# Maximum Subarray II ### Source - lintcode: [(42) Maximum Subarray II](http://www.lintcode.com/en/problem/maximum-subarray-ii/) ~~~ 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. Note The subarray should contain at least one number Challenge Can you do it in time complexity O(n) ? ~~~ ### 題解嚴格來講這道題這道題也可以不用動規來做，這里還是采用經典的動規解法。[Maximum Subarray](http://algorithm.yuanbin.me/zh-cn/dynamic_programming/maximum_subarray.html) 中要求的是數組中最大子數組和，這里是求不相重疊的兩個子數組和的和最大值，做過買賣股票系列的題的話這道題就非常容易了，既然我們已經求出了單一子數組的最大和，那么我們使用隔板法將數組一分為二，分別求這兩段的最大子數組和，求相加后的最大值即為最終結果。隔板前半部分的最大子數組和很容易求得，但是后半部分難道需要將索引從0開始依次計算嗎？NO!!! 我們可以采用從后往前的方式進行遍歷，這樣時間復雜度就大大降低了。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return: An integer denotes the sum of max two non-overlapping subarrays */ public int maxTwoSubArrays(ArrayList<Integer> nums) { // -1 is not proper for illegal input if (nums == null || nums.isEmpty()) return -1; int size = nums.size(); // get max sub array forward int[] maxSubArrayF = new int[size]; forwardTraversal(nums, maxSubArrayF); // get max sub array backward int[] maxSubArrayB = new int[size]; backwardTraversal(nums, maxSubArrayB); // get maximum subarray by iteration int maxTwoSub = Integer.MIN_VALUE; for (int i = 0; i < size - 1; i++) { // non-overlapping maxTwoSub = Math.max(maxTwoSub, maxSubArrayF[i] + maxSubArrayB[i + 1]); } return maxTwoSub; } private void forwardTraversal(List<Integer> nums, int[] maxSubArray) { int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE; int size = nums.size(); for (int i = 0; i < size; i++) { minSum = Math.min(minSum, sum); sum += nums.get(i); maxSub = Math.max(maxSub, sum - minSum); maxSubArray[i] = maxSub; } } private void backwardTraversal(List<Integer> nums, int[] maxSubArray) { int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE; int size = nums.size(); for (int i = size - 1; i >= 0; i--) { minSum = Math.min(minSum, sum); sum += nums.get(i); maxSub = Math.max(maxSub, sum - minSum); maxSubArray[i] = maxSub; } } } ~~~ ### 源碼分析前向搜索和逆向搜索我們使用私有方法實現，可讀性更高。注意是求非重疊子數組和，故求`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).