Maximum Subarray Sum using Divide and Conquer algorithm | A Divide and Conquer based program for maximum subarray sum problem ; 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 program to test maxSubArraySum
#include <limits.h> NEW_LINE #include <stdio.h> NEW_LINE int max ( int a , int b ) { return ( a > b ) ? a : b ; } int max ( int a , int b , int c ) { return max ( max ( a , b ) , c ) ; } int maxCrossingSum ( int arr [ ] , int l , int m , int h ) { int sum = 0 ; int left_sum = INT_MIN ; for ( int i = m ; i >= l ; i -- ) { sum = sum + arr [ i ] ; if ( sum > left_sum ) left_sum = sum ; } sum = 0 ; int right_sum = INT_MIN ; for ( int 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 ) ; } int maxSubArraySum ( int arr [ ] , int l , int h ) { if ( l == h ) return arr [ l ] ; int m = ( l + h ) / 2 ; return max ( maxSubArraySum ( arr , l , m ) , maxSubArraySum ( arr , m + 1 , h ) , maxCrossingSum ( arr , l , m , h ) ) ; } int main ( ) { int arr [ ] = { 2 , 3 , 4 , 5 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int max_sum = maxSubArraySum ( arr , 0 , n - 1 ) ; printf ( " Maximum ▁ contiguous ▁ sum ▁ is ▁ % d STRNEWLINE " , max_sum ) ; getchar ( ) ; return 0 ; }