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.

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