Maximum absolute difference between sum of two contiguous sub | Find maximum subarray sum for subarray [ 0. . i ] using standard Kadane ' s ▁ algorithm . ▁ This ▁ version ▁ ▁ of ▁ Kadane ' s Algorithm will work if all numbers are negative . ; Find maximum subarray sum for subarray [ i . . n ] using Kadane ' s ▁ algorithm . ▁ This ▁ version ▁ of ▁ Kadane ' s Algorithm will work if all numbers are negative ; The function finds two non - overlapping contiguous sub - arrays such that the absolute difference between the sum of two sub - array is maximum . ; create and build an array that stores maximum sums of subarrays that lie in arr [ 0. . . i ] ; create and build an array that stores maximum sums of subarrays that lie in arr [ i + 1. . . n - 1 ] ; Invert array ( change sign ) to find minumum sum subarrays . ; create and build an array that stores minimum sums of subarrays that lie in arr [ 0. . . i ] ; create and build an array that stores minimum sums of subarrays that lie in arr [ i + 1. . . n - 1 ] ; For each index i , take maximum of 1. abs ( max sum subarray that lies in arr [ 0. . . i ] - min sum subarray that lies in arr [ i + 1. . . n - 1 ] ) 2. abs ( min sum subarray that lies in arr [ 0. . . i ] - max sum subarray that lies in arr [ i + 1. . . n - 1 ] ) ; Driver Code
def maxLeftSubArraySum ( a , size , sum ) : NEW_LINE INDENT max_so_far = a [ 0 ] NEW_LINE curr_max = a [ 0 ] NEW_LINE sum [ 0 ] = max_so_far NEW_LINE for i in range ( 1 , size ) : NEW_LINE INDENT curr_max = max ( a [ i ] , curr_max + a [ i ] ) NEW_LINE max_so_far = max ( max_so_far , curr_max ) NEW_LINE sum [ i ] = max_so_far NEW_LINE DEDENT return max_so_far NEW_LINE DEDENT def maxRightSubArraySum ( a , n , sum ) : NEW_LINE INDENT max_so_far = a [ n ] NEW_LINE curr_max = a [ n ] NEW_LINE sum [ n ] = max_so_far NEW_LINE for i in range ( n - 1 , - 1 , - 1 ) : NEW_LINE INDENT curr_max = max ( a [ i ] , curr_max + a [ i ] ) NEW_LINE max_so_far = max ( max_so_far , curr_max ) NEW_LINE sum [ i ] = max_so_far NEW_LINE DEDENT return max_so_far NEW_LINE DEDENT def findMaxAbsDiff ( arr , n ) : NEW_LINE INDENT leftMax = [ 0 for i in range ( n ) ] NEW_LINE maxLeftSubArraySum ( arr , n , leftMax ) NEW_LINE rightMax = [ 0 for i in range ( n ) ] NEW_LINE maxRightSubArraySum ( arr , n - 1 , rightMax ) NEW_LINE invertArr = [ 0 for i in range ( n ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT invertArr [ i ] = - arr [ i ] NEW_LINE DEDENT leftMin = [ 0 for i in range ( n ) ] NEW_LINE maxLeftSubArraySum ( invertArr , n , leftMin ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT leftMin [ i ] = - leftMin [ i ] NEW_LINE DEDENT rightMin = [ 0 for i in range ( n ) ] NEW_LINE maxRightSubArraySum ( invertArr , n - 1 , rightMin ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT rightMin [ i ] = - rightMin [ i ] NEW_LINE DEDENT result = - 2147483648 NEW_LINE for i in range ( n - 1 ) : NEW_LINE INDENT absValue = max ( abs ( leftMax [ i ] - rightMin [ i + 1 ] ) , abs ( leftMin [ i ] - rightMax [ i + 1 ] ) ) NEW_LINE if ( absValue > result ) : NEW_LINE INDENT result = absValue NEW_LINE DEDENT DEDENT return result NEW_LINE DEDENT a = [ - 2 , - 3 , 4 , - 1 , - 2 , 1 , 5 , - 3 ] NEW_LINE n = len ( a ) NEW_LINE print ( findMaxAbsDiff ( a , n ) ) NEW_LINE