# 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. 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.

1. tempmailer says: