Maximum Sub array Sum using Divide and Conquer Approach
Jun 12, 2021
Before going to solve the problem first we should understand the problem π§
- Difficulty Level : Easy
- Step that follow divide and conquer method :-
- 1. Divide given array in two halves
- 2.maximum sub-array sum in left half
- 3.maximum sub-array sum in right half
- find the maximum sub-array in cross the midpoint
Example:- Array=[-4, -7, -1, 5,-2]
Output is 4, the sub array [-1, 5] has the maximum sum
You have given a array and find the maximum contiguous sum of the sub array.
Using Divide and Conquer approach, we can find the maximum sub array sum in O(nLogn) time.