Maximum subarray problem (Kadane’s algorithm)

Given an array of integers, find contiguous subarray within it which has the largest sum.

 

For example,


Input:  {-2, 1, -3, 4, -1, 2, 1, -5, 4}
Output: Subarray with the largest sum is {4, -1, 2, 1} with sum 6.

 


 

We can easily solve this problem in linear time using kadane’s algorithm. The idea is to maintain maximum (positive sum) sub-array “ending” at each index of the given array. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous index.

 
C++ implementation –
 

Download   Run Code

Output:

The sum of contiguous sub-array with the largest sum is 6

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 


 

Above code doesn’t handle the case when all elements of the array are negative. If the array contains all negative values, the answer is the maximum element. We can easily place this check before continuing to the algorithm. The implementation can be seen here.

But this approach requires two traversals of the input array. The main algorithm can also be easily modified to handle negative integers as well –

 
C++ implementation –
 

Download   Run Code

Output:

The sum of contiguous subarray with the largest sum is -2

 


 

Above code only prints the sum of contiguous subarray having the largest sum but do not print the subarray itself. We can easily modify the algorithm to keep track of the starting and ending indices of the maximum subarray.

 
C++ implementation –
 

Download   Run Code

Output:

The sum of contiguous sub-array with the largest sum is 6
The contiguous sub-array with the largest sum is 4 -1 2 1

 
The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).
 

Because of the way this algorithm uses optimal substructures (the maximum subarray ending at each position is calculated in a simple way from a related but smaller and overlapping subproblem: the maximum subarray ending at the previous position) this algorithm can be viewed as a simple example of dynamic programming.

 
References:
https://en.wikipedia.org/wiki/Maximum_subarray_problem
 

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 🙂