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
12
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
16
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,
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,
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:
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:
12
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.