.png)
Maximum Absolute Difference of Subarrays
Problem Statement
You are given an integer array arr of size n.
Find the maximum absolute difference between the sum of two non-overlapping contiguous subarrays, where one subarray is on the left and the other is on the right.
Example 1
Input
arr = [1, 2, -3, 1]
Output
6
Explanation
Left max sum = 3 → [1,2]
Right min sum = -3 → [-3]
[
|3 - (-3)| = 6
]
Why This Problem Is Important
- Extension of Kadane’s Algorithm
- Tests prefix & suffix preprocessing
- Frequently asked in Google / Amazon
- Core foundation for advanced range DP problems
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| 1 | Brute Force | O(n³) | O(1) |
| 2 | Prefix–Suffix Kadane | O(n) | O(n) |
Approach 1: Brute Force
Idea
- Try every possible left subarray
- Try every possible right subarray
- Ensure they do not overlap
- Compute |left_sum - right_sum|
- Track maximum
Time & Space
- Time: O(n³)
- Space: O(1)
Python
def maxAbsDifference(arr):
n = len(arr)
ans = 0
for i in range(n):
for j in range(i, n):
left_sum = sum(arr[i:j+1])
for x in range(j+1, n):
for y in range(x, n):
right_sum = sum(arr[x:y+1])
ans = max(ans, abs(left_sum - right_sum))
return ans
print(maxAbsDifference([1,2,-3,1]))
C++
#include
using namespace std;
int maxAbsDifference(vector& arr){
int n = arr.size();
int ans = 0;
for(int i=0;i arr = {1,2,-3,1};
cout << maxAbsDifference(arr);
}
Java
class Main {
public static int maxAbsDifference(int[] arr){
int n = arr.length;
int ans = 0;
for(int i=0;iJavaScript
function maxAbsDifference(arr){
let n = arr.length;
let ans = 0;
for(let i=0;iC#
using System;
class Program {
static int MaxAbsDifference(int[] arr){
int n = arr.Length;
int ans = 0;
for(int i=0;iOutput
6
Approach 2: Prefix & Suffix Kadane (Optimal)
Idea
We precompute 4 arrays:
- leftMax[i] → max subarray sum from 0 → i
- leftMin[i] → min subarray sum from 0 → i
- rightMax[i] → max subarray sum from i → n-1
- rightMin[i] → min subarray sum from i → n-1
Then for every split point i:
max(
|leftMax[i] - rightMin[i+1]|,
|leftMin[i] - rightMax[i+1]|
)
Time & Space
- Time: O(n)
- Space: O(n)
Python
def maxAbsDifference(arr):
n = len(arr)
leftMax = [0]*n
leftMin = [0]*n
rightMax = [0]*n
rightMin = [0]*n
# Left max
curr = leftMax[0] = arr[0]
for i in range(1,n):
curr = max(arr[i], curr+arr[i])
leftMax[i] = max(leftMax[i-1], curr)
# Left min
curr = leftMin[0] = arr[0]
for i in range(1,n):
curr = min(arr[i], curr+arr[i])
leftMin[i] = min(leftMin[i-1], curr)
# Right max
curr = rightMax[-1] = arr[-1]
for i in range(n-2,-1,-1):
curr = max(arr[i], curr+arr[i])
rightMax[i] = max(rightMax[i+1], curr)
# Right min
curr = rightMin[-1] = arr[-1]
for i in range(n-2,-1,-1):
curr = min(arr[i], curr+arr[i])
rightMin[i] = min(rightMin[i+1], curr)
ans = 0
for i in range(n-1):
ans = max(ans,
abs(leftMax[i] - rightMin[i+1]),
abs(leftMin[i] - rightMax[i+1]))
return ans
print(maxAbsDifference([1,2,-3,1]))
C++
#include
using namespace std;
int maxAbsDifference(vector& arr){
int n = arr.size();
vector leftMax(n), leftMin(n), rightMax(n), rightMin(n);
int curr = leftMax[0] = arr[0];
for(int i=1;i=0;i--){
curr = max(arr[i], curr + arr[i]);
rightMax[i] = max(rightMax[i+1], curr);
}
curr = rightMin[n-1] = arr[n-1];
for(int i=n-2;i>=0;i--){
curr = min(arr[i], curr + arr[i]);
rightMin[i] = min(rightMin[i+1], curr);
}
int ans = 0;
for(int i=0;i arr = {1,2,-3,1};
cout << maxAbsDifference(arr);
}
Java
class Main {
public static int maxAbsDifference(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];
int curr = leftMax[0] = arr[0];
for(int i=1;i=0;i--){
curr = Math.max(arr[i], curr + arr[i]);
rightMax[i] = Math.max(rightMax[i+1], curr);
}
curr = rightMin[n-1] = arr[n-1];
for(int i=n-2;i>=0;i--){
curr = Math.min(arr[i], curr + arr[i]);
rightMin[i] = Math.min(rightMin[i+1], curr);
}
int ans = 0;
for(int i=0;iJavaScript
function maxAbsDifference(arr){
let n = arr.length;
let leftMax = new Array(n);
let leftMin = new Array(n);
let rightMax = new Array(n);
let rightMin = new Array(n);
let curr = leftMax[0] = arr[0];
for(let i=1;i=0;i--){
curr = Math.max(arr[i], curr + arr[i]);
rightMax[i] = Math.max(rightMax[i+1], curr);
}
curr = rightMin[n-1] = arr[n-1];
for(let i=n-2;i>=0;i--){
curr = Math.min(arr[i], curr + arr[i]);
rightMin[i] = Math.min(rightMin[i+1], curr);
}
let ans = 0;
for(let i=0;iC#
using System;
class Program {
static int MaxAbsDifference(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];
int curr = leftMax[0] = arr[0];
for(int i=1;i=0;i--){
curr = Math.Max(arr[i], curr + arr[i]);
rightMax[i] = Math.Max(rightMax[i+1], curr);
}
curr = rightMin[n-1] = arr[n-1];
for(int i=n-2;i>=0;i--){
curr = Math.Min(arr[i], curr + arr[i]);
rightMin[i] = Math.Min(rightMin[i+1], curr);
}
int ans = 0;
for(int i=0;iOutput
6Final Summary
| Approach | Best Use Case |
|---|---|
| Brute Force | Learning & validation |
| Prefix–Suffix Kadane | Interview standard solution |
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.png)
