Description

Given an integer array, find a continuous subarray where the sum of numbers is the biggest. Your code should return the index of the first number and the index of the last number. (If their are duplicate answer, return anyone)

Example

Give[-3, 1, 3, -3, 4], return[1,4].

Solution

同Maximum Subarray I一样的思路，dp[i]用以记录以当前第i个数结尾的subarray的最大sum。那么dp[i]所代表的subarray end总是i， 用一个临时变量记录这个subarray的start，记为curStart。
什么时候更新curStart呢？当dp[i-1] + A[i] < A[i]即dp[i-1] < 0时，抛弃前面的所有数从第i个数字重新取subsrray，此时curStart更新为i
用变量max记录遍历过程中遇到的最大sum值，总是和dp[]进行比较，当dp[i] > max时更新max值，并记录下遍历到当前数字满足条件的subarray，起始index为curStart，终止index为i

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) {
        // Write your code here
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return ret;
        }

        int[] dp = new int[A.length];
        dp[0] = A[0];
        int max = A[0];
        int start = 0;
        int curStart = 0;
        int end = 0;

        for (int i = 1; i < A.length; i++) {
            dp[i] = Math.max(dp[i-1] + A[i], A[i]);
            if (dp[i-1] < 0) {
                curStart = i;
            }
            if (max < dp[i]) {
                max = dp[i];
                start = curStart;
                end = i;
            }
        }

        ret.add(start);
        ret.add(end);
        return ret;
    }
}