Continuous Subarray Sum 402

Question

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类似。

idea: 遍历数组，到i时，记录以i结尾的数组的最大值：

1) 若以i-1元素结尾的最大值小于0，则以i元素结尾的最大值为i元素

2) 若以i-1元素结尾的最大值大于等于0，则以i元素结尾的最大值为以i-1元素结尾的最大值加上i元素

代码如下：

// class Node{
//     int val;
//     int start;
//     int end;
//     public Node(int val, int start, int end){
//         this.val = val;
//         this.start = start;
//         this.end = end;
//     }
// }

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> result = new ArrayList<Integer>();
        result.add(-1);
        result.add(-1);
        if(A == null || A.length == 0){
            return result;
        }

        // Node[] DP = new Node[A.length];
        // DP[0] = new Node(A[0], 0, 0);
        // for(int i = 1; i < A.length; i++){
        //     if(DP[i - 1].val + A[i] > A[i]){
        //         DP[i] = new Node(DP[i - 1].val + A[i], DP[i - 1].start, i);
        //     }else{
        //         DP[i] = new Node(A[i], i, i);
        //     }
        // }

        // Node max = DP[0];
        // for(int i = 1; i < DP.length; i++){
        //     if(DP[i].val > max.val){
        //         max = DP[i];
        //     }
        // }

        int start = 0;
        int end = 0;
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < A.length; i++){
            if(sum < 0){
                sum = A[i];
                start = end = i;
            }else{
                sum = sum + A[i];
                end = i;
            }
            if(sum >= max){
                max = sum;
                result.set(0, start);
                result.set(1, end);
            }
        }

        // result.add(max.start);
        // result.add(max.end);
        return result;
    }
}