# Find maximum absolute difference between sum of two non-overlapping sub-arrays

Given an array, find the maximum absolute difference between sum of elements of two non-overlapping sub-arrays in linear time.

For example,

Input: A[] = { -3, -2, 6, -3, 5, -9, 3, 4, -1, -8, 2 }

Output: The maximum absolute difference is 19.

The two sub-arrays are { 6, -3, 5 }, { -9, 3, 4, -1, -8 } whose sum of elements are 8 and -11 respectively. So, abs(8-(-11)) or abs(-11-8) = 19.

The idea is to calculate the maximum and minimum sum of sub-arrays ending and starting at any index i of the array. Then for each index i, we consider the maximum absolute value of –

• Maximum sub-array sum in sub-array ending at index `i` – Minimum sub-array sum in sub-array starting at index `i+1`

• Minimum sub-array sum in sub-array ending at index `i` – Maximum sub-array sum in sub-array starting at index `i+1`

The time complexity of this solution is O(n2) if Kadane’s algorithm is used.

We can solve this problem in O(n) by using extra space. We create four auxiliary arrays, `left_min[i]`, `left_max[]`, `right_min[]`, `right_min[],` such that

• `left_max[i]` stores maximum sum of sub-array in `A(0, i)`
• `right_max[i]` stores maximum sum of sub-array in `A(i, n-1)`
• `left_min[i]` stores minimum sum of sub-array in `A(0, i)`
• `right_min[i]` stores minimum sum of sub-array in `A(i, n-1)`

To fill `left_max[]` and `right_max[]` arrays in linear time, we can use standard Kadane’s algorithm for finding the maximum sum of a sub-array.

To fill `left_min[]` and `right_min[]` arrays, we can still use the Kadane’s algorithm by transforming the array such that the sign of each element is reversed. Then we find the maximum sum of sub-array for each index, and invert its sign to get the minimum sub-array sum.

## C++

Output:

The maximum absolute difference is 19

## Java

Output:

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂