Given an integer array, find the maximum sum among all subarrays possible.

The problem differs from the problem of finding the maximum subsequence sum. Unlike subsequences, subarrays are required to occupy consecutive positions within the original array.

 
For example,

Input:  nums[] = [2, -4, 1, 9, -6, 7, -3]
 
Output: The maximum sum of the subarray is 11 (Marked in Green)

Practice this problem

A naive solution is to consider every possible subarray, find the sum, and take the maximum. The problem with this approach is that its worst-case time complexity is O(n2), where n is the size of the input.

Following is the C, Java, and Python program that demonstrates it:

C


Download  Run Code

Output:

The maximum sum of the subarray is 11

Java


Download  Run Code

Output:

The maximum sum of the subarray is 11

Python


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 technique 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 the left subarray,
  • Recursively calculate the maximum subarray sum for the right subarray,
  • Find the maximum subarray sum that crosses the middle element.
  • Return the maximum of the above three sums.

The algorithm can be implemented as follows in C, Java, and Python:

C


Download  Run Code

Output:

The maximum sum of the subarray is 11

Java


Download  Run Code

Output:

The maximum sum of the subarray is 11

Python


Download  Run Code

Output:

The maximum sum of the subarray is 11

The time complexity of the above divide-and-conquer solution is O(n.log(n)) as for the given array of size n, we make two recursive calls on input size n/2 and finding the maximum subarray crosses midpoint takes O(n) time in the worst case. Therefore,

T(n) = 2T(n/2) + O(n) = O(n.log(n))

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