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 Give [3, 1, -100, -3, 4], return [4,1].

思路

这道题加了一个条件，那就是可以把整个array看成是circular array，所以我们就需要考虑两种情况：一种情况是max sum subarray还是出现在普通array上，这种情况正常解题就可以，第二种情况是max sum subarray出现在circular array上，那么这时的解决办法就是求出min sum subarray，然后取补集得到max sum circular subarray。

复杂度

time O(n), space O(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
     */
    int[] globalOne;
    public ArrayList<Integer> continuousSubarraySumII(int[] A) {
        // Write your code here
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return result;
        }
        // preprocess
        int n = A.length;
        int[] local = new int[n];
        int[] global = new int[n];
        local[0] = global[0] = A[0];
        int start = 0;
        int[] res = new int[]{0, 0};
        // main
        for (int i = 1; i < n; i++) {
            int cur = A[i];
            int localCase1 = local[i - 1] + cur;
            int localCase2 = cur;
            if (localCase2 < localCase1) {
                start = i;
            }
            local[i] = Math.min(localCase1, localCase2);
            //global
            if (global[i - 1] > local[i]) {
                res = new int[]{start, i};
            }
            global[i] = Math.min(global[i - 1], local[i]);
            //System.out.println("i " + i + " " + res[0] + " " + res[1]);
        }
        //System.out.println(res[0] + " " + res[1]);
        ArrayList<Integer> temp1 = continuousSubarraySum(A);
        int sum = 0;
        for (int cur : A) {
            sum += cur;
        }
        if (globalOne[n - 1] > sum - global[n - 1]) {
            return temp1;
        }
        //System.out.println(globalOne[n - 1] + " " + (sum - global[n - 1]));
        //budao
        if (res[0] == 0 && res[1] == A.length - 1) {
            int max = Integer.MIN_VALUE;
            int maxIndex = 0;
            for (int i = 0; i < A.length; i++) {
                if (A[i] > max) {
                    max = A[i];
                    maxIndex = i;
                }
            }
            result.add(maxIndex);
            result.add(maxIndex);
            return result;
        }
        if (res[0] == 0) {
            result.add(res[1] + 1);
            result.add(A.length - 1);
            return result;
        }
        if (res[1] == A.length - 1) {
            result.add(0);
            result.add(res[0] - 1);
            return result;
        }
        result.add(res[1] + 1);
        result.add(res[0] - 1);
        return result;
    }

    public ArrayList<Integer> continuousSubarraySum(int[] A) {
        // Write your code here
        // check edge case
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (A == null || A.length == 0) {
            return result;
        }
        // preprocess
        int n = A.length;
        int[] local = new int[n];
        globalOne = new int[n];
        local[0] = globalOne[0] = A[0];
        int start = 0;
        int[] res = new int[]{0, 0};
        // main
        for (int i = 1; i < n; i++) {
            int cur = A[i];
            int localCase1 = local[i - 1] + cur;
            int localCase2 = cur;
            if (localCase2 > localCase1) {
                start = i;
            }
            local[i] = Math.max(localCase1, localCase2);
            //global
            if (globalOne[i - 1] < local[i]) {
                res = new int[]{start, i};
            }
            globalOne[i] = Math.max(globalOne[i - 1], local[i]);
            //System.out.println("i " + i + " " + res[0] + " " + res[1]);
        }
        result.add(res[0]);
        result.add(res[1]);
        return result;
    }
}