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).

Java

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.

Java

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.

(1 votes, average: 5.00 out of 5)