Continuous Subarray Sum II

reference: http://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Medium Continuous Subarray Sum II

10%

Accepted

Given an integer array, find a continuous rotate 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. The answer can be rorate array or non- rorate array)

Have you met this question in a real interview? 

Yes

Example

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

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> continuousSubarraySumII(int[] A) {
        // Write your code here
        
        Pair regular = continuousSubarraySum(A);
        int maxWrap = 0;
        
        for(int i = 0; i < A.length; i++){
            maxWrap += A[i];
            A[i] = -A[i];
        }
        Pair wrap = continuousSubarraySum(A);
        maxWrap = maxWrap + wrap.maxValue;
        ArrayList<Integer> temp = new ArrayList<Integer>();
        temp.add(wrap.idxs.get(1) + 1);
        temp.add(wrap.idxs.get(0) - 1);
        return maxWrap > regular.maxValue ?  temp : regular.idxs;
        
        
    }
    
    
    private Pair continuousSubarraySum(int[] A) {
        // Write your code here
        
        int curSum = A[0], maxSum = Integer.MIN_VALUE;
        int start = 0, end = 0;
        ArrayList<Integer> res = new ArrayList<Integer>();
        res.add(0);
        res.add(0);
        for(int i = 1; i < A.length; i++){
            if(maxSum < curSum){
                res.set(0, start);
                res.set(1, i-1);
                maxSum = curSum;
            } 
            if(curSum < 0){
                curSum = 0;
                start = i;
                end = i;
            }
            curSum += A[i];
             
        }
        
        if(maxSum < curSum){
            res.set(0, start);
            res.set(1, A.length - 1);
        }
        return new Pair(maxSum, res);
    }
    
    class Pair{
        int maxValue;
        ArrayList<Integer> idxs;
        public Pair(int maxValue, ArrayList<Integer> idxs){
            this.maxValue = maxValue;
            this.idxs = idxs;
            
        }
    }
}