Maximum Subarray Difference

Description

Given an array with integers.

Find twonon-overlapping_subarrays_A_and_B, which|SUM(A) - SUM(B)|is the largest.

Return the largest difference.

The subarray should contain at least one number

Example

For[1, 2, -3, 1], return6.

Challenge

O(n) time and O(n) space.

Analysis

与Maximum Subarray系列问题一样，这里其实只用转化问题即，求 max |SUM(A) - SUM(B)|，等价为求

Math.max(ans, Math.max(Math.abs(leftMax(A) - rightMin(B)), Math.abs(leftMin(A) - rightMax(B))))

也就是和之前求 maximum non-overlap subarrays 的思路基本一致，只不过要求的数组变成了四个：leftMax, leftMin, rightMax 和 rightMin

虽然最后代码很长，但是原理很简单，总共5 pass，4次pass用来生成leftMax, leftMin, rightMax 和 rightMin

最后一个pass用来寻找最终的答案。因此时间复杂度O(n), 空间复杂度O(n).

Solution

Kadane's Algorithm - O(n) space, O(n) time (283ms beats 96.40%!)

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer indicate the value of maximum difference between two substrings
     */
    public int maxDiffSubArrays(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int n = nums.length;
        int[] leftMax = new int[n];
        int[] leftMin = new int[n];
        int[] rightMax = new int[n];
        int[] rightMin = new int[n];

        leftMax[0] = nums[0];
        leftMin[0] = nums[0];
        rightMax[n - 1] = nums[n - 1];
        rightMin[n - 1] = nums[n - 1];

        int localMax = leftMax[0];
        int globalMax = leftMax[0];
        for (int i = 1; i < n; i++) {
            localMax = Math.max(localMax + nums[i], nums[i]);
            globalMax = Math.max(localMax, globalMax);
            leftMax[i] = globalMax;
        }

        int localMin = leftMin[0];
        int globalMin = leftMin[0];
        for (int i = 1; i < n; i++) {
            localMin = Math.min(localMin + nums[i], nums[i]);
            globalMin = Math.min(localMin, globalMin);
            leftMin[i] = globalMin;
        }

        localMax = rightMax[n - 1];
        globalMax = rightMax[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            localMax = Math.max(localMax + nums[i], nums[i]);
            globalMax = Math.max(localMax, globalMax);
            rightMax[i] = globalMax;
        }

        localMin = rightMin[n - 1];
        globalMin = rightMin[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            localMin = Math.min(localMin + nums[i], nums[i]);
            globalMin = Math.min(localMin, globalMin);
            rightMin[i] = globalMin;
        }

        int result = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            int temp = Math.max(Math.abs(leftMax[i] - rightMin[i + 1]), Math.abs(leftMin[i] - rightMax[i + 1]));
            result = Math.max(temp, result);
        }

        return result;
    }
}