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 below –

 

Download   Run Code

Output:

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

 

But this approach requires two traversals of the input array. We can easily modify the main algorithm to handle negative integers as well. The C++ implementation is shown below –

 

Download   Run Code

Output:

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

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 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Xenial
Guest
Xenial

I like this site as much as geeksforgeeks. Quality of post is definitely to the point and better. And, last but not the least, you guys have better font size and overall look of the site. Keep it up and thank you! 🙂

wpDiscuz