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, 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 i 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.

All possible subarrays of an array

Table-1: All possible subarrays of an array

  • Row number x in E_{x} indicates the ending index i for the subarray
  • Column number y in S_{y} 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 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 finding max(B_0, B_1, \ldots B_{n-1}) becomes a O(n) operation.

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\}) \\ \end{aligned}

If we consider the sum of all elements from index i to j as S_{(i)(j)}, we can rewrite the above equation as

\begin{aligned} \\ & 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(B_i + A_{i+1}, 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