Dive deep into Kadane’s algorithm​

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 i (call this B_i), what is the maximum subarray sum ending at position i+1 (equivalently, what is B_{i+1})? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position i+1 includes the maximum subarray sum ending at position i as a prefix, or it doesn’t (equivalently B_{i+1}=max(A_{i+1}, A_{i+1} + B_i), where A_{i+1} is the element at index i+1

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 &lte; 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
All possible subarrays of an array

Table-1: All possible subarrays of an array

From now on, if I refer to a row in the table, then I refer to all the subarrays in the i^{th} row and notice that all their ending index is i.

Q: How does knowing the maximum subarray sum of row i help us derive the maximum subarray sum of row i+1.

From the table, we know that the B_0 (the maximum subarray sum ending at 0) is nothing but the first element of the array. So, if we can somehow intelligently calculate the B_{i+1} by using B_i, then all that’s left is to find the max(B_0, B_1, \ldots B_{n-1}). Without further ado, let’s get started.

The maximum subarray sum of row i can be mathematically represented as

\begin{aligned} \\ & B_i = max(\{A_0 + A_1 + \ldots + A_i\}, \{A_1 + A_2 + \ldots + A_i\} \ldots \{A_i\}) \\ & \qquad or \\ & B_i = max(S_{(0)(i)}, S_{(1)(i)}, \ldots S_{(i)(i)}) \\ \end{aligned}

If you look carefully in the table, all the subarrays but the last one in the {i+1}^{th} row are nothing but subarrays found in i^{th} row with an extra element A_{i+1} slapped on at the end of each subarray. Oh, and the last subarray is a singleton array \{A_{i+1}\}.

\begin{aligned} \\ & B_{i+1} = max(\{A_0 + A_1 + \ldots A_i + A_{i+1}\}, \{A_1 + \ldots + A_i + A_{i+1}\} \ldots \{A_i + A_{i+1}\}, \{A_{i+1}\}) \\ & \qquad or \\ & B_{i+1} =  max(\{S_{(0)(i)} + A_{i+1}\}, \{S_{(1)(i)} + A_{i+1}\}, \ldots \{S_{(i)(i)} + A_{i+1}\}, \{A_{i+1}\}) \\ & \qquad or \\ & B_{i+1} =  max(max(\{S_{(0)(i)} + A_{i+1}\}, \{S_{(1)(i)} + A_{i+1}\}, \ldots \{S_{(i)(i)} + A_{i+1}\}), \{A_{i+1}\}) \\ \end{aligned}

Another not so common property of max that I’d like you to think about is max(a + z, b + z, \ldots, y + z) = max(a, b, \ldots y) + z.

By using the above property, we can replace max(\{S_{(0)(i)} + A_{i+1}\}, \{S_{(1)(i)} + A_{i+1}\}, \ldots \{S_{(i)(i)} + A_{i+1}\}) in the previous equation with max(S_{(0)(i)}, S_{(1)(i)}, \ldots S_{(i)(i)}) + A_{i+1} to get

B_{i+1} = max(A_{i+1}, B_i + A_{i+1})

So with just high school mathematics, we’ve proved the induction.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s