Could you discuss about the divide and conquer approach for this problem too ?
Maximum sum subarray
to solve it using divide and conquer
1) Divide the given array in two halves
2) Return the maximum of following three
…. a) Maximum subarray sum in left half (Make a recursive call)
…. b) Maximum subarray sum in right half (Make a recursive call)
…. c) Maximum subarray sum such that the subarray crosses the midpoint
The lines 2.a and 2.b are simple recursive calls.
How to find maximum subarray sum such that the subarray crosses the midpoint?
We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1.
Finally, combine the two and return.