Lintcode 45. Maximum Subarray Difference

题目

Given an array with integers.

Find two non-overlapping subarrays A and B, which |SUM(A) - SUM(B)| is the largest.

Return the largest difference.

Example For [1, 2, -3, 1], return 6.

思路

这道题因为是找两个none-overlapping的subarray，本质上还是枚举分割线，然后在分割线左右的区间内分别去找max sum and min sum，因为max diff可以是由leftMax - rightMin or leftMin - rightMax得出的。

复杂度

time O(n), space O(n)

代码

  public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two
     *          Subarrays
     */
    public int maxDiffSubArrays(int[] nums) {
        // write your code here
        if (nums == null || nums.length == 0) {
            return Integer.MIN_VALUE;
        }
        // pre-process
        int len = nums.length;
        int[] localMax = new int[len];
        int[] localMin = new int[len];
        int[] leftGlobalMax = new int[len];
        int[] leftGlobalMin = new int[len];
        localMax[0] = localMin[0] = leftGlobalMin[0] = leftGlobalMax[0] = nums[0];
        for (int i = 1; i < len; i++) {
            int cur = nums[i];
            localMin[i] = Math.min(localMin[i - 1] + cur, cur);
            localMax[i] = Math.max(localMax[i - 1] + cur, cur);
            leftGlobalMin[i] = Math.min(leftGlobalMin[i - 1], localMin[i]);
            leftGlobalMax[i] = Math.max(leftGlobalMax[i - 1], localMax[i]);
        }
        localMax = new int[len];
        localMin = new int[len];
        int[] rightGlobalMin = new int[len];
        int[] rightGlobalMax = new int[len];
        localMax[len - 1] = localMin[len - 1] = rightGlobalMin[len - 1] = rightGlobalMax[len - 1] = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            int cur = nums[i];
            localMin[i] = Math.min(localMin[i + 1] + cur, cur);
            localMax[i] = Math.max(localMax[i + 1] + cur, cur);
            rightGlobalMin[i] = Math.min(rightGlobalMin[i + 1], localMin[i]);
            rightGlobalMax[i] = Math.max(rightGlobalMax[i + 1], localMax[i]);
        }
        // main loop
        int maxResult = 0;
        for (int i = 0; i < len - 1; i++) {
            int s1 = Math.abs(leftGlobalMin[i] - rightGlobalMax[i + 1]);
            int s2 = Math.abs(leftGlobalMax[i] - rightGlobalMin[i + 1]);
            maxResult = Math.max(maxResult, s1);
            maxResult = Math.max(maxResult, s2);
        }
        return maxResult;
    }
}