Maximum Sum Subarray using Divide & Conquer

Given an array of integers, find maximum sum subarray among all subarrays possible.

 
For example,


Input:  A[]= [2, -4, 1, 9, -6, 7, -3]

Output:The Maximum sum of the subarray is 11 (Marked in Green)

 


 

Naive solution would be to consider every possible subarray and find sum of all of them and take maximum. The problem with this approach is that its worst case time complexity is O(n2).

 
C++ implementation –
 

Download   Run Code

Output:

The Maximum sum of the subarray is 11

 

How can we perform better?

 

The idea is to use divide and conquer to find the maximum subarray sum. The algorithm works as follows –

  • Divide the array into two equal subarrays.
  • Recursively calculate the maximum subarray sum for left subarray.
  • Recursively calculate the maximum subarray sum for right subarray.
  • Find the maximum subarray sum that crosses mid element.
  • Return the maximum of above three sums.

 
C++ implementation –
 

Download   Run Code

Output:

The Maximum sum of the subarray is 11

 

Maximum Sum Subarray Solution Performance –

 
The time complexity of above D&C solution is O(nlogn) as for given array of size n, we make two recursive calls on input size n/2 and finding maximum subarray that crosses midpoint takes O(n) time in worst case. So,

    T(n) = 2T(n/2) + O(n)
    T(n) = O(nlogn)

 
We can also solve this problem in O(n) time using Kadane’s algorithm.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz