Problem

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

思路一

• 从左往右计算前缀的时候,
  • 遇到负数的前缀和, 设置为当前值
  • 否则, 加上当前值
• 举例:
  • [-3, 1, 3, -3, 4]
  • ps[1] = -3, 所以清零

    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        ArrayList<Integer> result = new ArrayList<>();

        if (A == null || A.length == 0) {
            return result;    
        }

        int sum = 0;
        int ans = Integer.MIN_VALUE;
        int start = 0; 
        int end = 0;
        result.add(start);
        result.add(end);

        for (int i = 0; i < A.length; i++) {
            if (sum < 0) {
                sum = A[i];
                start = i;
                end = i;
            } else {
                sum += A[i];
                end = i;
            }

            if (sum > ans) {
                ans = sum;
                result.set(0, start);
                result.set(1, end);
            }

        }
        return result;
    }

思路2

• sum = ps[i] - ps[j], j < i
• 每当遍历数组, 当前前缀和减去它之前的最小的前缀和, 然后取最大的sum, 便是答案

O(n ^ 2) solution

    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        ArrayList<Integer> result = new ArrayList<>();

        if (A == null || A.length == 0) {
            return result;    
        }

        int n = A.length;
        int[] ps = new int[n + 1];
        int max = Integer.MIN_VALUE;

        for (int i = 1; i <= n; i++) {
            ps[i] = ps[i - 1] + A[i - 1];
            for (int j = 0; j < i; j++) {
                int sum = ps[i] - ps[j];
                if (max < sum) {
                    max = sum;
                    result.clear();
                    result.add(j);
                    result.add(i - 1);
                }

            }
        }

        return result;
    }

优化

    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        ArrayList<Integer> result = new ArrayList<>();

        if (A == null || A.length == 0) {
            return result;    
        }

        int n = A.length;
        int[] ps = new int[n + 1];
        int max = Integer.MIN_VALUE;
        int min = 0;
        int minIndex = -1;

        for (int i = 1; i <= n; i++) {
            ps[i] = ps[i - 1] + A[i - 1];
            int sum = ps[i] - min;
            if (max < sum) {
                max = sum;
                result.clear();
                result.add(minIndex + 1);
                result.add(i - 1);                
            }
            // System.out.println(minIndex + ": " + min);
            if (min >= ps[i]) {
                min = ps[i];
                minIndex = i - 1;
            }
        }

        return result;
    }