I am writing this post as I could not find any reliable material that could clearly explain the intuition behind Kadane’s algorithm.
To start, here’s a (very) crisp explanation of Kadane’s algorithm from Wikipedia.
Kadane’s algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position (call this ), what is the maximum subarray sum ending at position (equivalently, what is ? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position includes the maximum subarray sum ending at position as a prefix, or it doesn’t (equivalently , where is the element at index
Unfortunately, when you see this explanation, it is hard to convince yourself why the algorithm works. Here is my attempt to make this explanation more easy to digest.
Q: Does this algorithm cover all subarrays?
Answering the above question is quite simple. It all depends on how you traverse over all the possible subarrays.
Generally, when you ask a programmer to iterate over all the subarrays, they’ll iterate over the inner loop by keeping the outer loop’s current iteration value constant. Here’s a code snippet that shows this idea.
for (int i = 0; i < n; ++i) for (int j = i; j < n; ++j) // Do something with subarray [i, j]
Another not so uncommon way of iterating is to use the outer loop’s current iteration value as an upper bound in the inner loop. Here’s how I’d put that in code.
for (int i = 0; i < n; ++i) for (int j = 0; j <e; i; ++j) // Do something with subarray [j, i]
Just to drive this concept home, let’s visualize the loop again as a table.
- Row number y in Ey indicates the ending index (i) for the subarray
- Column number x in Sx indicates the starting index (j) for the subarray
From now on, if I refer to a row in the table, then I refer to all the subarrays in the row and notice that all their ending index is .
Q: How does knowing the maximum subarray sum of row help us derive the maximum subarray sum of row .
From the table, we know that the (the maximum subarray sum ending at 0) is nothing but the first element of the array. So, if we can somehow intelligently calculate the by using , then all that’s left is to find the . Without further ado, let’s get started.
The maximum subarray sum of row can be mathematically represented as
If you look carefully in the table, all the subarrays but the last one in the row are nothing but subarrays found in row with an extra element slapped on at the end of each subarray. Oh, and the last subarray is a singleton array .
Another not so common property of that I’d like you to think about is .
By using the above property, we can replace in the previous equation with to get
So with just high school mathematics, we’ve proved the induction.