# Maximum Subarray ### Source - leetcode: [Maximum Subarray | LeetCode OJ](https://leetcode.com/problems/maximum-subarray/) - lintcode: [(41) Maximum Subarray](http://www.lintcode.com/en/problem/maximum-subarray/) ~~~ Given an array of integers, find a contiguous subarray which has the largest sum. Example Given the array [?2,2,?3,4,?1,2,1,?5,3], the contiguous subarray [4,?1,2,1] has the largest sum = 6. Note The subarray should contain at least one number. Challenge Can you do it in time complexity O(n)? ~~~ ### 題解1 - 貪心 求最大子數組和，即求區間和的最大值，不同子區間共有約 n2n^2n2 中可能，遍歷雖然可解，但是時間復雜度頗高。 這里首先介紹一種巧妙的貪心算法，用`sum`表示當前子數組和，`maxSum`表示求得的最大子數組和。當`sum <= 0`時，累加數組中的元素只會使得到的和更小，故此時應將此部分和丟棄，使用此時遍歷到的數組元素替代。需要注意的是由于有`maxSum`更新`sum`, 故直接丟棄小于0的`sum`并不會對最終結果有影響。即不會漏掉前面的和比后面的元素大的情況。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ public int maxSubArray(ArrayList<Integer> nums) { // -1 is not proper for illegal input if (nums == null || nums.isEmpty()) return -1; int sum = 0, maxSub = Integer.MIN_VALUE; for (int num : nums) { // drop negtive sum sum = Math.max(sum, 0); sum += num; // update maxSub maxSub = Math.max(maxSub, sum); } return maxSub; } } ~~~ ### 源碼分析 貪心的實現較為巧妙，需要`sum`和`maxSub`配合運作才能正常工作。 ### 復雜度分析 遍歷一次數組，時間復雜度 O(n)O(n)O(n), 使用了幾個額外變量，空間復雜度 O(1)O(1)O(1). ### 題解2 - 動態規劃1(區間和) 求最大/最小這種字眼往往都可以使用動態規劃求解，此題為單序列動態規劃。我們可以先求出到索引 i 的子數組和，然后用子數組和的最大值減去最小值，最后返回最大值即可。用這種動態規劃需要注意初始化條件和求和順序。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ public int maxSubArray(ArrayList<Integer> nums) { // -1 is not proper for illegal input if (nums == null || nums.isEmpty()) return -1; int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE; for (int num : nums) { minSum = Math.min(minSum, sum); sum += num; maxSub = Math.max(maxSub, sum - minSum); } return maxSub; } } ~~~ ### 源碼分析 首先求得當前的最小子數組和，初始化為0，隨后比較子數組和減掉最小子數組和的差值和最大區間和，并更新最大區間和。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 使用了類似滾動數組的處理方式，空間復雜度 O(1)O(1)O(1). ### 題解3 - 動態規劃2(局部與全局) 這種動規的實現和題解1 的思想幾乎一模一樣，只不過這里用局部最大值和全局最大值兩個數組來表示。 ### Java ~~~ public class Solution { /** * @param nums: A list of integers * @return: A integer indicate the sum of max subarray */ public int maxSubArray(ArrayList<Integer> nums) { // -1 is not proper for illegal input if (nums == null || nums.isEmpty()) return -1; int size = nums.size(); int[] local = new int[size]; int[] global = new int[size]; local[0] = nums.get(0); global[0] = nums.get(0); for (int i = 1; i < size; i++) { // drop local[i - 1] < 0 local[i] = Math.max(nums.get(i), local[i - 1] + nums.get(i)); // update global with local global[i] = Math.max(global[i - 1], local[i]); } return global[size - 1]; } } ~~~ ### 源碼分析 由于局部最大值需要根據之前的局部值是否大于0進行更新，故方便起見初始化 local 和 global 數組的第一個元素為數組第一個元素。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 空間復雜度也為 O(n)O(n)O(n). ### Reference - 《劍指 Offer》第五章 - [Maximum Subarray 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/maximum-subarray/)