# Continuous Subarray Sum ### Source - lintcode: [(402) Continuous Subarray Sum](http://www.lintcode.com/en/problem/continuous-subarray-sum/) ### Problem Given an integer array, find a continuous subarray where the sum of numbers isthe biggest. Your code should return the index of the first number and theindex of the last number. (If their are duplicate answer, return anyone) #### Example Give `[-3, 1, 3, -3, 4]`, return `[1,4]`. ### 題解 和題 [Maximum Subarray](http://algorithm.yuanbin.me/zh-cn/dynamic_programming/maximum_subarray.html) 幾乎一模一樣，只是返回值要求不一樣。由于需要返回區間索引值，那么顯然需要額外變量記錄區間起止處。若使用題解2中提到的`sum - minSum`的區間和更新方式，索引終止處容易得知是`sum - minSum > maxSub`時的`i`, 問題是索引起始處如何確定。容易得知索引起始處如果更新，必然在`minSum > sum`時，但問題在于滿足此條件的可能不止一處，所以我們需要先記錄這個索引值并在`sum - minSum > maxSub`時判定索引終止值是否大于索引起始值，不小于則更新。 此題難以一次 bug-free, 需要小心更新索引值。 ### 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> continuousSubarraySum(int[] A) { ArrayList<Integer> result = new ArrayList<Integer>(); if (A == null || A.length == 0) return result; int sum = 0, minSum = 0, maxSub = Integer.MIN_VALUE; int first = 0, last = 0; int first2 = 0; // candidate for first for (int i = 0; i < A.length; i++) { if (minSum > sum) { minSum = sum; first2 = i; } sum += A[i]; if (sum - minSum > maxSub) { maxSub = sum - minSum; last = i; // update first if valid if (first2 <= last) first = first2; } } result.add(first); result.add(last); return result; } } ~~~ ### 源碼分析 除了最后要求的`first`和`last`, 我們還需要引入`first2`作為`first`可能的候選變量值。 ### 復雜度分析 略