Maximum Subarray Sum using Divide and Conquer algorithm | Find the maximum possible sum in arr [ ] such that arr [ m ] is part of it ; Include elements on left of mid . ; Include elements on right of mid ; Return sum of elements on left and right of mid returning only left_sum + right_sum will fail for [ - 2 , 1 ] ; Returns sum of maximum sum subarray in aa [ l . . h ] ; Base Case : Only one element ; Find middle point ; Return maximum of following three possible cases a ) Maximum subarray sum in left half b ) Maximum subarray sum in right half c ) Maximum subarray sum such that the subarray crosses the midpoint ; Driver Code
< ? php function maxCrossingSum ( & $ arr , $ l , $ m , $ h ) { $ sum = 0 ; $ left_sum = PHP_INT_MIN ; for ( $ i = $ m ; $ i >= $ l ; $ i -- ) { $ sum = $ sum + $ arr [ $ i ] ; if ( $ sum > $ left_sum ) $ left_sum = $ sum ; } $ sum = 0 ; $ right_sum = PHP_INT_MIN ; for ( $ i = $ m + 1 ; $ i <= $ h ; $ i ++ ) { $ sum = $ sum + $ arr [ $ i ] ; if ( $ sum > $ right_sum ) $ right_sum = $ sum ; } return max ( $ left_sum + $ right_sum , $ left_sum , $ right_sum ) ; } function maxSubArraySum ( & $ arr , $ l , $ h ) { if ( $ l == $ h ) return $ arr [ $ l ] ; $ m = intval ( ( $ l + $ h ) / 2 ) ; return max ( maxSubArraySum ( $ arr , $ l , $ m ) , maxSubArraySum ( $ arr , $ m + 1 , $ h ) , maxCrossingSum ( $ arr , $ l , $ m , $ h ) ) ; } $ arr = array ( 2 , 3 , 4 , 5 , 7 ) ; $ n = count ( $ arr ) ; $ max_sum = maxSubArraySum ( $ arr , 0 , $ n - 1 ) ; echo " Maximum ▁ contiguous ▁ sum ▁ is ▁ " . $ max_sum ; ? >