Lintcode 403. Continuous Subarray Sum II

Given an circular integer array (the next element of the last element is the first element), find a continuous subarray in it, 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 duplicate answers exist, return any of them.

Example

Example 1:

Input: [3, 1, -100, -3, 4]
Output: [4, 1]

Example 2:

Input: [1,-1]
Output: [0, 0]

Challenge

O(n) time

Code (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 List<Integer> continuousSubarraySumII(int[] A) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (A == null || A.length == 0) {
            return ans;
        }
        
        ResultType maxResult = findMax(A, 1);
        ResultType minResult = findMax(A, -1);
        
        int sum = 0;
        for (int num : A) {
            sum += num;
        }
        
        if (maxResult.max >= sum - minResult.max) {
            ans.add(maxResult.leftIdx);
            ans.add(maxResult.rightIdx);
        } else {
            // corner case: all A[i] is negative
            if (sum == minResult.max) {
                int maxVal = Integer.MIN_VALUE;
                int k = 0;
                for (int i = 0; i < A.length; i++) {
                    if (A[i] > maxVal) {
                        maxVal = A[i];
                        k = i;
                    }
                }
                ans.add(k);
                ans.add(k);
            } else {
                ans.add(minResult.rightIdx + 1);
                ans.add(minResult.leftIdx - 1);
            }
        }
        
        return ans;
    }
    
    private ResultType findMax(int[] A, int coef) {
        int sum = 0;
        int maxSum = Integer.MIN_VALUE;
        int preMinSum = 0;
        int preMinIdx = -1;
        
        ResultType ans = new ResultType(-1, -1, -1);
        
        for (int i = 0; i < A.length; i++) {
            sum += A[i] * coef;
            
            if (sum - preMinSum > maxSum) {
                maxSum = sum - preMinSum;
                ans.max = maxSum;
                ans.leftIdx = preMinIdx + 1;
                ans.rightIdx = i;
            }
            
            if (preMinSum > sum) {
                preMinSum = sum;
                preMinIdx = i;
            }
        }
        
        ans.max = ans.max * coef;
        
        return ans;
    }
}

class ResultType {
    int max;
    int leftIdx;
    int rightIdx;
    
    ResultType(int max, int leftIdx, int rightIdx) {
        this.max = max;
        this.leftIdx = leftIdx;
        this.rightIdx = rightIdx;
    }
}