Maximum Subarray Sum using Divide and Conquer algorithm | A Divide and Conquer based Java program for maximum subarray sum problem ; 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 program to test maxSubArraySum
import java . util . * ; class GFG { static int maxCrossingSum ( int arr [ ] , int l , int m , int h ) { int sum = 0 ; int left_sum = Integer . MIN_VALUE ; for ( int i = m ; i >= l ; i -- ) { sum = sum + arr [ i ] ; if ( sum > left_sum ) left_sum = sum ; } sum = 0 ; int right_sum = Integer . MIN_VALUE ; for ( int i = m + 1 ; i <= h ; i ++ ) { sum = sum + arr [ i ] ; if ( sum > right_sum ) right_sum = sum ; } return Math . max ( left_sum + right_sum , Math . max ( left_sum , right_sum ) ) ; } static int maxSubArraySum ( int arr [ ] , int l , int h ) { if ( l == h ) return arr [ l ] ; int m = ( l + h ) / 2 ; return Math . max ( Math . max ( maxSubArraySum ( arr , l , m ) , maxSubArraySum ( arr , m + 1 , h ) ) , maxCrossingSum ( arr , l , m , h ) ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 3 , 4 , 5 , 7 } ; int n = arr . length ; int max_sum = maxSubArraySum ( arr , 0 , n - 1 ) ; System . out . println ( " Maximum ▁ contiguous ▁ sum ▁ is ▁ " + max_sum ) ; } }