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
< ? php function maxLeftSubArraySum ( & $ a , $ size , & $ sum ) { $ max_so_far = $ a [ 0 ] ; $ curr_max = $ a [ 0 ] ; $ sum [ 0 ] = $ max_so_far ; for ( $ i = 1 ; $ i < $ size ; $ i ++ ) { $ curr_max = max ( $ a [ $ i ] , $ curr_max + $ a [ $ i ] ) ; $ max_so_far = max ( $ max_so_far , $ curr_max ) ; $ sum [ $ i ] = $ max_so_far ; } return $ max_so_far ; } function maxRightSubArraySum ( & $ a , $ n , & $ sum ) { $ max_so_far = $ a [ $ n ] ; $ curr_max = $ a [ $ n ] ; $ sum [ $ n ] = $ max_so_far ; for ( $ i = $ n - 1 ; $ i >= 0 ; $ i -- ) { $ curr_max = max ( $ a [ $ i ] , $ curr_max + $ a [ $ i ] ) ; $ max_so_far = max ( $ max_so_far , $ curr_max ) ; $ sum [ $ i ] = $ max_so_far ; } return $ max_so_far ; } function findMaxAbsDiff ( & $ arr , $ n ) { $ leftMax = array_fill ( 0 , $ n , NULL ) ; maxLeftSubArraySum ( $ arr , $ n , $ leftMax ) ; $ rightMax = array_fill ( 0 , $ n , NULL ) ; maxRightSubArraySum ( $ arr , $ n - 1 , $ rightMax ) ; $ invertArr = array_fill ( 0 , $ n , NULL ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ invertArr [ $ i ] = - $ arr [ $ i ] ; $ leftMin = array_fill ( 0 , $ n , NULL ) ; maxLeftSubArraySum ( $ invertArr , $ n , $ leftMin ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ leftMin [ $ i ] = - $ leftMin [ $ i ] ; $ rightMin = array_fill ( 0 , $ n , NULL ) ; maxRightSubArraySum ( $ invertArr , $ n - 1 , $ rightMin ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ rightMin [ $ i ] = - $ rightMin [ $ i ] ; $ result = PHP_INT_MIN ; for ( $ i = 0 ; $ i < $ n - 1 ; $ i ++ ) { $ absValue = max ( abs ( $ leftMax [ $ i ] - $ rightMin [ $ i + 1 ] ) , abs ( $ leftMin [ $ i ] - $ rightMax [ $ i + 1 ] ) ) ; if ( $ absValue > $ result ) $ result = $ absValue ; } return $ result ; } $ a = array ( -2 , -3 , 4 , -1 , -2 , 1 , 5 , -3 ) ; $ n = sizeof ( $ a ) ; echo findMaxAbsDiff ( $ a , $ n ) ; ? >