Kadane's Algorithm to solve Maximum Subarray Problem With Examples

Maximum Subarray Problem is a famous problem in dynamic programming. The algorithm we use to solve this problem is known as Kadane’s algorithm. It is a slightly tricky algorithm to understand but don’t you worry. This tutorial we go over the algorithm in an easy to understand manner.

What is the Maximum Subarray Problem?

This problem requires you to find the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.

The array will contain negative integers. If the array only contains positive integers then the answer will be the sum of the complete array.

Kadane’s Algorithm

The Kadane’s Algorithm solves this problem by traversing over the entire array and keeping two variables to track the sum so far and overall maximum.

The conditions under which each of the two variables are updated are important.

Let’s look at the algorithm :

  1. Initialize max_so_far = 0
  2. Initialize max_ending_here = 0
  3. Repeat steps 4 to 6 for each element of the array
  4. set max_ending_here = max_ending_here + a[i]
  5. if(max_ending_here < 0) then set max_ending_here = 0
  6. if(max_so_far < max_ending_here) then set max_so_far = max_ending_here
  7. return max_so_far

That’s Kadane’s algorithm in six seven easy steps.

We can summarize the update criteria in two sentences :

When the variable max_ending_here becomes negative, we set it to zero. At each iteration, we check for max_so_far < max_ending_here, if the condition is true then we update max_so_far.

The for loop for steps 4 to 6 will be :


Let’s look at an example :

Kadane’s Algorithm

The maximum subarray is from i=2 to i=6. The maximum sum is 7.

Kadane’s algorithm Implementation

The complete code for Kadane’s algorithm is as follows, in the code we have printed the values of max_so_far and max_ending_here at each step.

1. Java

2. C++

Kadane’s Algorithm


This tutorial was about Kadane’s algorithm. If you’re interested in more problems like this, you should check our tutorial on subset sum problem.

By admin

Leave a Reply

%d bloggers like this: