402.Continuous Subarray Sum

1.Description(Medium)

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].

2.Code

这道题我们要及时更新start和end变量，分别为子数组的起始和结束位置。我们用curSum来记录当前位置的累计和，如果某一个位置之前的累计和为负数，那么我们直接从当前位置开始重新算即可，因为加上负数还不如不加，此时将start和end都更新为当前位置i；如果之前的累计和大于等于0，那么我们把累计和curSum再加上当前的数字，然后更新end位置为i。此时我们更新最大子数组之和mx，以及res即可

这个题要maxStart, maxEnd, start, 那么我们直接从当前位置开始重新算即可，因为加上负数还不如不加,所以我们把start更新成i,如果之前的累计和大于等于0，那么我们把累计和curSum再加上当前的数字。如果这个时候比maxValue大了，就把maxEnd更新成i,再把之前记录的start 变成maxStart.

这个题目要多记录一个start.因为不确定当前prefix虽然小，但是是不是差值是答案。

 public ArrayList<Integer> continuousSubarraySum(int[] A) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return result;
        }
        int currentSum = 0;
        int maxValue = Integer.MIN_VALUE;
        int maxStart = 0;
        int maxEnd = 0;
        int start = 0;
        for (int i = 0; i < A.length; ++i) {
            if (currentSum < 0) {
                currentSum = A[i];
                start = i;
            }else {
                currentSum += A[i];
            }
            if (maxValue < currentSum) {
                maxValue = currentSum;
                maxStart = start;
                maxEnd = i;
            }
        }
        result.add(maxStart);
        result.add(maxEnd);
        return result;
    }