proof | thirumal's blog

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.

Continue reading “Dive deep into Kadane’s algorithm” →