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.

Challenge:

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

Example:

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

Solution:

This is an extension of Maximum Subarray II. We need to calculate max and min from both front and back. Four sets of sums are required maxLeft, minLeft, maxRight, minRight. The final difference could be calculated by

differ = Math.max(differ, Math.max(
                      Math.abs(maxLeft[i] - minRight[i + 1]),
                      Math.abs(minLeft[i] = maxRight[i + 1])
                      ))

Code:

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: An integer denotes the sum of max two non-overlapping subarrays
     */
    public int maxTwoSubArrays(ArrayList<Integer> nums) {
        if (nums == null || nums.size() == 0) {
            return 0;
        }
        int n = nums.size();

        int[] maxLeft = new int[n];
        int sum = 0;
        int minSum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            maxLeft[i] = max;
        }
        int[] maxRight = new int[n];
        sum = 0;
        minSum = 0;
        max = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            sum += nums.get(i);
            max = Math.max(max, sum - minSum);
            minSum = Math.min(minSum, sum);
            maxRight[i] = max;
        }
        printArray(maxLeft);
        printArray(maxRight);

        max = Integer.MIN_VALUE;
        for (int i = 0; i < n - 1; i++) {
            max = Math.max(max, maxLeft[i] + maxRight[i + 1]);
        }
        return max;
    }

    private void printArray(int[] array) {
        for (int x : array) {
            System.out.print(x + ",");
        }
        System.out.println("");
    }
}