Max Absolute Diff of Two Subarrays

Problem Overview

Two chosen subarrays must not overlap, so place a split between them.

Intuition

Two chosen subarrays must not overlap, so place a split between them. For a fixed split, the largest absolute difference must use opposite extremes: either the maximum subarray sum on the left minus the minimum on the right, or the minimum on the left minus the maximum on the right. Kadane’s algorithm can maintain all four extremes across every split in linear time.

Algorithm

1Run Kadane’s algorithm from right to left to build maxRight[i], the maximum subarray sum wholly inside suffix i…n−1.
2In the same reverse pass, use the minimum-sum form of Kadane to build minRight[i].
3Scan split positions i from left to right, maintaining maxLeftSoFar and minLeftSoFar for prefix 0…i.
4At each split, evaluate |maxLeftSoFar − minRight[i+1]| and |minLeftSoFar − maxRight[i+1]|.
5Return the largest difference seen across all n−1 valid splits.

Example Walkthrough

Input: arr = [1, 2, -3, 4, 5]

1. Consider the split between -3 and 4. In the left prefix, the minimum-sum subarray is [-3] with sum -3.
2. In the right suffix, the maximum-sum subarray is [4,5] with sum 9.
3. Their absolute difference is |-3−9| = 12.
4. Checking every split with the precomputed suffix extrema finds no larger value, so the answer is 12.

Output: 12

Common Pitfalls

• The two subarrays must be non-empty and non-overlapping; only split at i where i+1 exists.
• Track both maximum and minimum subarray sums — comparing only two maxima misses large positive-versus-negative gaps.
• Use Kadane states for contiguous subarrays, not prefix sums for arbitrary subsequences.
• Initialize states from actual array elements rather than 0 so all-negative and all-positive arrays work correctly.
• The implementation returns 0 for n < 2 because two non-empty disjoint subarrays cannot be formed.

Max Absolute Diff of Two Subarrays.java

Java


class Solution {

    // Approach: Use Kadane's algorithm from right to left to precompute the
    // maximum and minimum subarray sums in every suffix. Then scan split points
    // left to right while maintaining the corresponding prefix extrema. For each
    // split, compare left maximum with right minimum and left minimum with right
    // maximum; one of these opposite-extreme pairs gives the best absolute gap.
    // Complexity: O(n) time and O(n) auxiliary space.
    public int maxDiffSubArrays(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return 0;
        }
        // Space Optimization: Only precompute right (suffix) values
        int[] maxRight = new int[n];
        int[] minRight = new int[n];
        // 1. Precompute right values (Suffix)
        int currentMax = arr[n - 1], maxSoFar = arr[n - 1];
        int currentMin = arr[n - 1], minSoFar = arr[n - 1];
        maxRight[n - 1] = maxSoFar;
        minRight[n - 1] = minSoFar;

        for (int i = n - 2; i >= 0; i--) {
            currentMax = Math.max(arr[i], currentMax + arr[i]);
            maxSoFar = Math.max(maxSoFar, currentMax);
            maxRight[i] = maxSoFar;
            currentMin = Math.min(arr[i], currentMin + arr[i]);
            minSoFar = Math.min(minSoFar, currentMin);
            minRight[i] = minSoFar;
        }

        // 2. Compute left values on the fly and find the max difference
        int maxDiff = Integer.MIN_VALUE;
        int currentMaxLeft = arr[0], maxLeftSoFar = arr[0];
        int currentMinLeft = arr[0], minLeftSoFar = arr[0];
        for (int i = 0; i < n - 1; i++) {
            // Update left values up to index i
            if (i > 0) {
                currentMaxLeft = Math.max(arr[i], currentMaxLeft + arr[i]);
                maxLeftSoFar = Math.max(maxLeftSoFar, currentMaxLeft);
                currentMinLeft = Math.min(arr[i], currentMinLeft + arr[i]);
                minLeftSoFar = Math.min(minLeftSoFar, currentMinLeft);
            }

            // Calculate differences with the precomputed right values at i + 1
            int diff1 = Math.abs(maxLeftSoFar - minRight[i + 1]);
            int diff2 = Math.abs(minLeftSoFar - maxRight[i + 1]);
            maxDiff = Math.max(maxDiff, Math.max(diff1, diff2));
        }

        return maxDiff;
    }
}

Was this solution helpful?