取反

Continuous Subarray Sum II

为什么不能用重复：自己开始写的不对 因为最后的解 (start,end) 之间的距离不能超过原来的长度。所以仅仅是拼接数组然后按照DP的做法扫一个整个数组是不行的。。而是应该扫N个子数组(以不同起点长度为n的数组扫) 但是这样的话时间复杂度就是N方 所以不如取反的做法

     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
        ArrayList<Integer> result = new ArrayList<Integer>();
        result.add(0);
        result.add(0);
        //total record the sum of all the element of A
        int total = 0;
        int len = A.length;
        int start = 0, end = 0;
        int local = 0;
        int global = Integer.MIN_VALUE;
        //find the max sum in between 
        for (int i = 0; i < len; ++i) {
            total += A[i];
            if (local < 0) {
                local = A[i];
                start = end = i;
            } else {
                local += A[i];
                end = i;
            }
            if (local >= global) {
                global = local;
                result.set(0, start);
                result.set(1, end);
            }
        }

        local = 0;
        start = 0;
        end = -1;
        //find the min sum in between update the result if (total - min) > previous max sum
        for (int i = 0; i < len; ++i) {
            if (local > 0) {
                local = A[i];
                start = end = i;
            } else {
                local += A[i];
                end = i;
            }
            if (start == 0 && end == len-1) continue;
            if (total - local >= global) {
                global = total - local;
                result.set(0, (end + 1) % len);
                result.set(1, (start - 1 + len) % len);
            }
        }
        return result;
    }
}