# 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:

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂