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, but once I prove it to you,​ then it’ll seem trivial. 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 probably write something like this.

for (int i = 0; i < n; ++i)
{
    for (int j = i; j < n; ++j)
    {
        // Do something with subarray [i, j]
        // OBSERVE: All subarrays start with index `i`
    }
}

Another not so uncommon way of iterating is to use as a termination condition in the inner loop, like so

for (int i = 0; i < n; ++i)
{
    for (int j = 0; j < i; ++j)
    {
        // Do something with subarray [j, i]
        // OBSERVE: All subarrays end with index `i`
    }
}

Just to drive this concept home, let’s visualise this​ as a table. Each cell is a subarray (i.e. one iteration of the inner loop), and each row is one iteration of the outer loop.

• Row number in indicates the ending index for the subarray
• Column number in indicates the starting index 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 finding becomes a operation.

The maximum subarray sum of row can be mathematically represented as

If we consider the sum of all elements from index to as , we can rewrite the above equation 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.