Disclaimer: If you are looking for a quick read before an interview, this article is not for you. However, please feel free to bookmark this page and come back later.
Recently, I interviewed a candidate and asked him a problem which finally boiled down to a variant of maximum subarray problem. He was able to recognize it as such and also able to walk me through his implementation of Kadane’s algorithm explaining how it works. When I asked him if he could tell why this algorithm works, he could not give me a definitive answer. After the interview, while I was walking him out, he did confess that he’d just blindly accepted whatever Wikipedia had told him. As soon as I was back in my seat, I searched for this on Wikipedia, and here is what I found.
Kadane’s algorithm begins with a simple inductive question: if we know the maximum subarray sum ending at position (call this ), what is the maximum subarray sum ending at position (equivalently, what is ? The answer turns out to be relatively straightforward: either the maximum subarray sum ending at position includes the maximum subarray sum ending at position as a prefix, or it doesn’t (equivalently , where is the element at index
Their explanation was perfect and to the point. So much so, if I’d glanced over a single word without reasoning about it, I would have missed the point on why the algorithm works the way it does. I did search around on the Internet for decent explanations, the only person whose explanation was helpful was the one by CS Dojo, but even his attempt of proving the algorithm just touched the tip of the iceberg.
My aim in this article is to not only expand upon these brief explanations but take you on a small journey where you experience the problem in different lights and finally figure out the algorithm yourself.