Maximum Subarray Sum using Divide and Conquer algorithm | A utility function to find maximum of two integers ; A utility function to find maximum of three integers ; Find the maximum possible sum in arr [ ] auch 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
function max ( a , b ) { return ( a > b ) ? a : b ; } function max ( a , b , c ) { return Math . max ( Math . max ( a , b ) , c ) ; } function maxCrossingSum ( arr , l , m , h ) { let sum = 0 ; let left_sum = Number . MIN_VALUE ; for ( let i = m ; i >= l ; i -- ) { sum = sum + arr [ i ] ; if ( sum > left_sum ) left_sum = sum ; } sum = 0 ; let right_sum = Number . MIN_VALUE ; for ( let 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 ] ; let m = parseInt ( ( l + h ) / 2 , 10 ) ; return max ( maxSubArraySum ( arr , l , m ) , maxSubArraySum ( arr , m + 1 , h ) , maxCrossingSum ( arr , l , m , h ) ) ; } let arr = [ 2 , 3 , 4 , 5 , 7 ] ; let n = arr . length ; let max_sum = maxSubArraySum ( arr , 0 , n - 1 ) ; document . write ( " " + max_sum ) ;