Maximum Subarray Sum using Divide and Conquer algorithm | 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
def maxCrossingSum ( arr , l , m , h ) : NEW_LINE INDENT sm = 0 NEW_LINE left_sum = - 10000 NEW_LINE for i in range ( m , l - 1 , - 1 ) : NEW_LINE INDENT sm = sm + arr [ i ] NEW_LINE if ( sm > left_sum ) : NEW_LINE INDENT left_sum = sm NEW_LINE DEDENT DEDENT sm = 0 NEW_LINE right_sum = - 1000 NEW_LINE for i in range ( m + 1 , h + 1 ) : NEW_LINE INDENT sm = sm + arr [ i ] NEW_LINE if ( sm > right_sum ) : NEW_LINE INDENT right_sum = sm NEW_LINE DEDENT DEDENT return max ( left_sum + right_sum , left_sum , right_sum ) NEW_LINE DEDENT def maxSubArraySum ( arr , l , h ) : NEW_LINE INDENT if ( l == h ) : NEW_LINE INDENT return arr [ l ] NEW_LINE DEDENT m = ( l + h ) // 2 NEW_LINE return max ( maxSubArraySum ( arr , l , m ) , maxSubArraySum ( arr , m + 1 , h ) , maxCrossingSum ( arr , l , m , h ) ) NEW_LINE DEDENT arr = [ 2 , 3 , 4 , 5 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE max_sum = maxSubArraySum ( arr , 0 , n - 1 ) NEW_LINE print ( " Maximum ▁ contiguous ▁ sum ▁ is ▁ " , max_sum ) NEW_LINE