An Intuitive Approach to Understanding Kadane’s Algorithm.

My rant about what’s wrong with how it’s taught and an unorthodox introduction to Dynamic Programming.

Photo by Blake Connally on Unsplash

We are given an array of integers nums[]and our task is to determine the maximum sum we can obtain by selecting a contiguous segment of the array and do it in O(n)time. To lead by example:

nums[] = {-1, 2, 3, -4, 5}
^ ^
start end
output : 6

Here is a link to the LeetCode problem. This problem is often introduced as an introductory one in a DSA101 and in other beginner algorithmic classes.

Right off the bat, if you google Kadane's Algorithm you will be presented with this O(n) in time and O(1) in space solution.

Not intuitive in the least. There is no hint as to what the motivation behind the solution was. But this is what our instructors probably shoved down our throats. At least mine did. This specific snippet is taken from geeksforgeeks. But don’t worry, I do not expect you to read it, let alone understand it. We will be working our way up to this.

It would be audacious of me to go about claiming that this article builds up to the optimal solution without first discussing the suboptimal one. So let’s briefly discuss the O(n^2) solution. The pseudocode to it looks somewhat like this:

int sum = 0, globalmax = 0;
for i in {0... nums.size() - 1}:
sum = 0;
for j in {i... nums.size() - 1}:
sum += nums[j];
globalsum = max(sum, globalsum);
return globalsum;

The basic idea here is to compute sum for each subarray starting at i for each i in range(0, nums.size()-1) and maintaining our globalsum as the maximum of all the values of sum that were computed. This however costs us O(n^2) time. Not so hot.

The most profound hint that you may or may not have noticed is that the linear time solution presented by gfg snippet is actually a highly optimised dynamic programming approach. Hence, we are going to treat it as one. So if you’re not familiar with DP, this is an excellent place to start; however, if you are, feel free to skip the quoted text below.

Top-Down Dynamic Programming is simply an optimisation over recursion. If we can come-up with a recursive solution to a problem, breaking it down to smaller subproblems and the subproblems are overlapping i.e. the recursive call demands the solution to same subproblems multiple times, we can often cache or store the solutions to them so that in subsequent recusive calls we might not waste computation time in calculating results to the problems we previously did.

The most intuitive DP solutions are top-down recursive ones, we’ll be doing just that. Working with our original example:

nums[] = {-1, 2, 3, -4, 5}

The question that we will be asking ourselves here is:

If the size of our array was n-1, what will be the maximum subarray sum we can obtain if the subarray was to end at our last index ?

let’s assume that somehow we have computed the answer to this question. Now that we have the maximum subarray sum for the array of size n-1we can easily compute the maximum subarray sum for an array of size n if the subarray was to end at this new array’s (of size n ) last index.
We only have two choices

  • Either we can extend the maximum subarray ending for the array of
    n-1elements by adding our current last element.
  • Or we can start a new subarray here with just the element at n-1th index in it.

out of these two choices, we will pick the maximum.

For example:

nums[] = {-1, 2, 3, -4, 5} // let's assume n = 3
^

we can easily see that the maximum subarray sum ending at the last index of the array of n-1size would be 2 let’s call this value R. Now we have two choices either we can extend our previous subarray i.e 3 + R or we can take just 3 . Obviously, since we are trying to maximise we will choose the maximum of these i.e max(3, 3 + R) // this will give 5 . Now again when we get to n = 4 we will be presented with the same choice. REMEMBER THE QUESTION. Either we could extend our previous answer and get
5 + (-4) = -1 or we can start a new subarray here with just the element in it i.e -4 the max(-1, -4) = -1 and so on.

Cool, so now we have broken down our problem into neat little subproblems. we can write the pseudo-code somewhat like:

int GetMaxSub(int nums[], int n):
// base case
return max(nums[n - 1], nums[n - 1] + GetMaxSub(nums, n - 1))

We still have two problems here.

  • To find the base case in a recursive scenario, I like to think what the smallest possible input could be that we can feed to the recursive function. The answer to that here obviously is an array with just 1 element in it. The result to that should simply be the element itself so we can safely add that as the base case.
int GetMaxSub(int nums[], int n):
if(n == 1) return a[n - 1] //base case
return max(nums[n - 1], nums[n - 1] + GetMaxSub(nums, n - 1)

before moving on to the next problem with our solution, let’s discuss the complexity here. For any nwhen GetMaxSubwill be called, it will call for
n-1, then n-2, n-3,.... 1 . Also, there will be no branching anywhere in the recursive call tree, therefore we can evidently say that the algorithm runs in linear time. For space complexity, There is a call-stack overhead of order O(n) .

  • Let’s recall what our original question was, for any n that we call our GetMaxSub, it will return the maximum subarray sum among the subarrays that end at the last index, i.e n-1. What we actually want however is the global maximum subarray, which could obviously end at any index. The solution to this could be to either calculate GetMaxSubfor every i in range(1, nums.size())and return the maximum among all of those like this:
int gmax = INT32_MIN
for i in range(1, nums.size()):
gmax = max(gmax, GetMaxSub(nums, i)
return gmax

which would clearly defeat the purpose of building up the elegant recursive solution because the overall complexity would again be O(n^2) but the key here is to note that we are making redundant calculations. calling GetMaxSub(nums, nums.size()) already calculates the maximum subarray sum for subarrays ending at all the different positions. We could just store those computations.

We will create an array called dp[](gotta stick to culture, eh?) and since when we call GetMaxSub(nums, nums.size()), it will be calculating results to the maximum subarray sum for subarrays ending at all i in range(0, nums.size()-1) i.e we can make dp[i] store the maximum of all subarray sum ending at index i(and that was what we discovered our subproblems to be). After that, we can simply traverse the dp array and return the maximum of all the elements stored in it.

The working C++code:

this is exactly the solution that the gfg snippet gives us, with just some recursive call-stack overhead. However, the underlying approach is the same, implementation is the only difference, which will not be difficult to come around once the approach is intuitive. For e.g, we don’t actually need dp to be an array but it could be a simple int variable which we can keep updating. The call stack could be eliminated by implementing the approach with a for or a while loop. These modifications, however, are left as an excercise for the reader. For now, in the next post, whenever that may be, we will be deriving the solution to the maximum product subarray problem from this exact code.

Engineer-in-making by the day, hobbyist writer by the night. A bit of both during weekends.