Max Absolute Difference of Two Subarrays (Kadane's Algorithm)

Introduction

Finding the maximum subarray sum is one of the most common interview problems, and it is efficiently solved using Kadane's Algorithm. But what if the problem becomes slightly more challenging?

Suppose you're asked to find two non-overlapping contiguous subarrays such that the absolute difference between their sums is as large as possible.

At first glance, this appears to be a brute-force problem because there are many possible subarray combinations. However, with a clever application of Kadane's Algorithm, we can solve it in linear time (O(n)), making it suitable even for arrays containing 100,000 or more elements.

In this article, we'll explore the intuition, derive the optimal approach, walk through an example, and implement the complete Java solution.

Problem Statement

Given an integer array arr[], find two non-overlapping contiguous subarrays such that the absolute difference between their sums is maximum.

Example 1

Input

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

Output

Explanation

Choose the following non-overlapping subarrays:

[-2, -3]          Sum = -5

[4, -1, -2, 1, 5] Sum = 7

The absolute difference is:

|7 - (-5)| = 12

Example 2

Input

arr = [2, -1, -2, 1, -4, 2, 8]

Output

Why the Brute-Force Approach Doesn't Work

A straightforward solution would be:

Generate every possible subarray.
Compare every pair of non-overlapping subarrays.
Compute the absolute difference of their sums.

Unfortunately,

Number of subarrays = O(n²)
Comparing every pair = O(n⁴)

For large arrays, this approach is computationally infeasible.

Instead, we need an algorithm that processes the array only a few times.

Key Observation

Imagine splitting the array after every index.

0 1 2 3 4 5 6

| Left | Right |

For any split,

The first subarray must lie entirely in the left part.
The second subarray must lie entirely in the right part.

Instead of checking every possible subarray repeatedly, we only need to know the best possible subarray on each side of every split.

This idea allows us to preprocess the array once and evaluate every split efficiently.

The Four Helper Arrays

To answer every split efficiently, we build four arrays.

1. leftMax

leftMax[i] stores the maximum subarray sum within the range:

0 ... i

Example:

Array
-2 -3  4 -1 -2  1  5 -3

leftMax
-2 -2  4  4  4  4  7  7

At index 6, the maximum subarray is:

[4, -1, -2, 1, 5]

Sum = 7

2. leftMin

leftMin[i] stores the minimum subarray sum from index 0 to i.

leftMin

-2 -5 -5 -5 -5 -5 -5 -5

The minimum subarray is:

[-2, -3]

Sum = -5

3. rightMax

rightMax[i] stores the maximum subarray sum from:

i ... n-1

7 7 7 5 5 5 5 -3

4. rightMin

rightMin[i] stores the minimum subarray sum from:

i ... n-1

-5 -3 -3 -3 -2 -3 -3 -3

Why Do We Need Four Arrays?

Suppose, for a particular split, we have:

Left Side
Maximum = 10
Minimum = -6

Right Side
Maximum = 12
Minimum = -8

There are only two combinations capable of producing the largest absolute difference.

Case 1

Largest positive on the left versus largest negative on the right.

|Left Maximum - Right Minimum|

|10 - (-8)| = 18

Case 2

Largest negative on the left versus largest positive on the right.

|Left Minimum - Right Maximum|

|-6 - 12| = 18

Therefore, for every split, we only evaluate:

Math.abs(leftMax[i] - rightMin[i + 1])

Math.abs(leftMin[i] - rightMax[i + 1])

The maximum of these values is our answer.

Building the Helper Arrays

Building `leftMax`

We use the standard Kadane's Algorithm.

int currMax = arr[0];
leftMax[0] = arr[0];

for (int i = 1; i < n; i++) {

    currMax = Math.max(arr[i], currMax + arr[i]);

    leftMax[i] = Math.max(leftMax[i - 1], currMax);
}

How Kadane's Algorithm Works

At every element, there are only two choices:

Start a new subarray from the current element.
Extend the previous subarray.

currMax = Math.max(arr[i], currMax + arr[i]);

Then keep track of the best result seen so far.

leftMax[i] = Math.max(leftMax[i - 1], currMax);

Building `leftMin`

The logic is identical, except we look for the minimum sum.

currMin = Math.min(arr[i], currMin + arr[i]);

leftMin[i] = Math.min(leftMin[i - 1], currMin);

Building `rightMax`

Traverse the array from right to left.

currMax = arr[n - 1];

for (int i = n - 2; i >= 0; i--) {

    currMax = Math.max(arr[i], currMax + arr[i]);

    rightMax[i] = Math.max(rightMax[i + 1], currMax);
}

Building `rightMin`

Similarly,

currMin = arr[n - 1];

for (int i = n - 2; i >= 0; i--) {

    currMin = Math.min(arr[i], currMin + arr[i]);

    rightMin[i] = Math.min(rightMin[i + 1], currMin);
}

Computing the Final Answer

Once all helper arrays are available, evaluate every possible split.

int ans = 0;

for (int i = 0; i < n - 1; i++) {

    ans = Math.max(ans,
            Math.abs(leftMax[i] - rightMin[i + 1]));

    ans = Math.max(ans,
            Math.abs(leftMin[i] - rightMax[i + 1]));
}

Since each split is processed once, this step also runs in O(n) time.

Dry Run

Consider the input:

[-2, -3, 4, -1, -2, 1, 5, -3]

After preprocessing, the helper arrays become:

Index	leftMax	leftMin	rightMax	rightMin
0	-2	-2	7	-5
1	-2	-5	7	-3
2	4	-5	7	-3
3	4	-5	5	-3
4	4	-5	5	-2
5	4	-5	5	-3
6	7	-5	5	-3
7	7	-5	-3	-3

Now evaluate every split.

The largest value obtained is:

Complete Java Solution

class Solution {

    public int maxDiffSubArrays(int[] arr) {

        int n = arr.length;

        int[] leftMax = new int[n];
        int[] leftMin = new int[n];
        int[] rightMax = new int[n];
        int[] rightMin = new int[n];

        // Maximum subarray from left
        int currMax = arr[0];
        leftMax[0] = arr[0];

        for (int i = 1; i < n; i++) {
            currMax = Math.max(arr[i], currMax + arr[i]);
            leftMax[i] = Math.max(leftMax[i - 1], currMax);
        }

        // Minimum subarray from left
        int currMin = arr[0];
        leftMin[0] = arr[0];

        for (int i = 1; i < n; i++) {
            currMin = Math.min(arr[i], currMin + arr[i]);
            leftMin[i] = Math.min(leftMin[i - 1], currMin);
        }

        // Maximum subarray from right
        currMax = arr[n - 1];
        rightMax[n - 1] = arr[n - 1];

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

        // Minimum subarray from right
        currMin = arr[n - 1];
        rightMin[n - 1] = arr[n - 1];

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

        int ans = 0;

        for (int i = 0; i < n - 1; i++) {

            ans = Math.max(ans,
                    Math.abs(leftMax[i] - rightMin[i + 1]));

            ans = Math.max(ans,
                    Math.abs(leftMin[i] - rightMax[i + 1]));
        }

        return ans;
    }
}

Complexity Analysis

Metric	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

The array is traversed four times to build the helper arrays and once more to evaluate every split, resulting in linear time complexity.

Key Takeaways

Kadane's Algorithm can be extended to compute both maximum and minimum subarray sums.
Preprocessing the array from both directions allows every possible split to be evaluated efficiently.
Only two combinations need to be checked for each split:
- |leftMax − rightMin|
- |leftMin − rightMax|
This optimization reduces the brute-force O(n⁴) solution to an efficient O(n) algorithm.
The approach is ideal for competitive programming and technical interviews where input sizes can be very large.

Conclusion

Although the problem initially appears to require comparing every pair of subarrays, the key insight is that each split only depends on the best maximum and minimum subarrays on either side. By combining four preprocessed arrays with Kadane's Algorithm, we can solve the problem in linear time while keeping the implementation clean and easy to understand.

This technique demonstrates how a classic algorithm like Kadane's can be adapted to solve more advanced array problems, making it a valuable pattern for coding interviews and competitive programming.