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++

Download   Run Code

Output:

The maximum absolute difference is 19

Java

Download   Run Code

Output:


 
Thanks for reading.

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 🙂
 






Leave a Reply

avatar
  Subscribe  
Notify of