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

# Continuous Subarray Sum II ### Source - lintcode: [(403) Continuous Subarray Sum II](http://www.lintcode.com/en/problem/continuous-subarray-sum-ii/) - [Maximum circular subarray sum - GeeksforGeeks](http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/) ### Problem Given an integer array, find a continuous rotate subarray where the sum ofnumbers is the biggest. Your code should return the index of the first numberand the index of the last number. (If their are duplicate answer, returnanyone. The answer can be rorate array or non- rorate array) #### Example Give `[3, 1, -100, -3, 4]`, return `[4,1]`. ### 題解題 [Continuous Subarray Sum](http://algorithm.yuanbin.me/zh-cn/problem_misc/continuous_subarray_sum.html) 的 follow up, 這道題 AC 率極低，真是磨人的小妖精。在上題的基礎上容易想到可以將`first`和`last`分四種情況討論，然后再逆向求大于0的最大和即可，但是這種想法忽略了一種情況——旋轉后的最大值可能由兩段子數組和構成，而這種情況如果用上題的解法則會被忽略。所以這道題的正確解法不是分`first`和`last`四種情況討論，而是利用旋轉數組的特性。第一種情況，無論怎么拼接原數組中的數組和都無法大于最大的單一數組和；第二種情況則相反。所以現在問題的關鍵則轉化為怎么求第二種情況。首先可以明確一點，最終得到的數組和索引必須連續（含首尾相接）。也就是說情況二一旦出現，則我們可以將原數組中挖空一小段，現在問題來了：到底要挖掉多少元素？ **我們的目標是使得挖掉后的元素值最大。**由于分段求解不容易（被隔開），但是被挖掉的元素索引是挨著的！正難則反！由于數組的總和是一定的，那么我們只要求得被挖掉部分元素的最小值即可得兩邊子數組的最大值！最后判斷兩個最大值孰大孰小就可以了。 ### Java ~~~ public class Solution { /** * @param A an integer array * @return A list of integers includes the index of the first number and the index of the last number */ public ArrayList<Integer> continuousSubarraySumII(int[] A) { ArrayList<Integer> result = new ArrayList<Integer>(); if (A == null || A.length == 0) return result; // maximal subarray sum ArrayList<Integer> sub1 = subSum(A, 1); // minimal subarray sum ArrayList<Integer> sub2 = subSum(A, -1); int first = 0, last = 0; if (sub1.get(3) - sub2.get(2) > sub1.get(2)) { last = sub2.get(0) - 1; first = sub2.get(1) + 1; } else { first = sub1.get(0); last = sub1.get(1); } // corner case(all elements are negtive) if (last == -1 && first == A.length) { first = sub1.get(0); last = sub1.get(1); } result.add(first); result.add(last); return result; } private ArrayList<Integer> subSum(int[] A, int sign) { ArrayList<Integer> result = new ArrayList<Integer>(); // find the max/min subarray sum from [0...A.length] int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE; if (sign == -1) maxSub = Integer.MAX_VALUE; int first = 0, last = 0; int first2 = 0; // candidate for first for (int i = 0; i < A.length; i++) { if (sign * minSum > sign * sum) { minSum = sum; first2 = i; } sum += A[i]; if (sign * (sum - minSum) > sign * maxSub) { maxSub = sum - minSum; last = i; // update first if valid if (first2 <= last) first = first2; } } result.add(first); result.add(last); result.add(maxSub); result.add(sum); return result; } } ~~~ ### 源碼分析由于既需要求最大子數組和，也需要求最小子數組和，我們將這一部分寫成一私有方法，并加入`sign`控制符號。如果兩段子數組和大于一段子數組和時，新的`first`和`last`正好相反。且在數組全為負時需要排除，直接使用單一子數組和最大的情況。 ### 復雜度分析遍歷兩次數組，時間復雜度 O(n)O(n)O(n), 使用了部分額外 List, 空間復雜度 O(1)O(1)O(1). ### Reference - [CC150+Leetcode Continuous Subarray Sum II](http://meetqun.com/thread-9856-1-1.html)