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++

Download   Run Code

Output:

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

Java

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 in C++ and Java –

C++

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

The sum of contiguous subarray 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++ and Java implementation is shown below –

C++

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

The sum of contiguous sub-array 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.

 
Related Post: Print continuous subarray with maximum sum
 

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (3 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Xenial
Guest

I like this site more than every other coding site. 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! 🙂

FunniestClown
Guest

True that.
I come here whenever I feel confused in g4g 😉

tom
Guest

The fact that every problem here “can be easily solved” makes me feel quite stupid. lol

ssap
Guest

Is Kadane Algorithm Divide and Conquer too? Sorry if this is a stupid question. Thanks

Ankit
Guest

Kadane’s algorithm is a Dynamic programming algorithm, not Divide & Conquer.

foobar
Guest

I think 2 & 3 solutions were swapped.

Lucas
Guest

In first solution, you can check greater first then check negative result. This will work for all negative number array.