Dynamic Programming – Kadane’s Algorithm

Hello people..! In this post, we will look at a simple dynamic programming based algorithm which is the optimal solution to the Maximum Sum Subarray Problem. Try to focus on how the approach of dynamic programming is applied rather than just trying to understand the main algorithm. Now, let us define the problem.

Maximum Sum Subarray – Given an array A[1, 2, 3, … n]. We need to find that subarray A'[i, i + 1, i + 2, … j] where 1 ≤ i ≤ j ≤ n, where the sum of all the elements in A’ is maximum.

In simpler terms, we need to find that contiguous portion of an array where the sum is maximum.

Brute force approach

Brute force approach would be to look at all the sub-arrays starting with A[i] –

This is algorithm is simple but it takes O(N²) time. The problem with this algorithm is that we are not able to save computation by using the solutions to the problems we already solved.

Let us re-write this algorithm slightly differently! Pay attention! Instead of starting from A[i] and going forward looking for maximum, this time, let us start at A[i] and go backward doing the same thing, finding the maximum. Here is the algorithm –

What we are doing is instead of looking at all the sub-arrays starting with A[i], we will look at all the sub-arrays ending with A[i]. This still runs in O(N²) time. So, what’s so special about this? Let is say we have an array A = {-1, 2, 3, -4}. The above algorithm would work on this algorithm something like this –

• for i = 1 ⇒ max( sum(-1) )
• for i = 2 ⇒ max ( sum(2), sum(2, -1) )
• for i = 3 ⇒ max ( sum(3), sum(3, 2), sum(3, 2, -1) )
• for i = 4 ⇒ max ( sum(-4), sum(-4, 3), sum(-4, 3, 2), sum(-4, 3, 2, -1) )

The solution would be the maximum of all iterations. If you notice, in each iteration, we are finding the maximum sum of all the sub-arrays ending with A[i]. Let us say we store this result in an array maxSum[i].

Kadane’s Algorithm states that,

In simple terms, it states that, the maximum sum sub-array ending with A[i], is either the element A[i] itself, or A[i] combined with the maximum sum sub-array ending with A[i – 1], whichever is the greater one.

Ponder upon this for a while. Using the above intuition we can re-write the above iterations as –

• for i = 1 ⇒ max ( -1 ) ⇒ maxSum[1] = -1
• for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum[2] = 2
• for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum[3] = 5
• for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum[4] = 1

And as before, the solution would be the maximum of all the elements in maxSum array. For the sake of simplicity, we used the array maxSum[], but we only need the previous iteration’s result to compute the current iteration result. So, we can make it a variable. So our iterations change into –

• for i = 1 ⇒ maxSum = -1
• for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum = 2
• for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum = 5
• for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum = 1

Why was the first iteration written like that? It is the trivial case. The maximum sum sub-array ending with the first element is the first element itself. And for each iteration, we could keep a global variable, say maxGlobalSum, which keeps track of maximum of all maxSum values.

If you have understood everything up to now, you should be able to code the algorithm very easily. If you didn’t understand, please give a couple more readings and try to code again. Feel free to ask your doubts in the comments!

If you are stuck with the algorithm, you can use my code as a reference –

This algorithm runs in O(N) time and uses O(1) space. I hope you have developed an idea of how to think in the dynamic programming way. To get a dynamic programming algorithm, we just have to analyse if where we are computing things which we have already computed and how can we reuse the existing solutions. Keep practising..! Happy Coding! 😀