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:


 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

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 🙂
 



Leave a Reply

avatar
  Subscribe  
Notify of