Maximum Sub array Sum using Divide and Conquer Approach

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.