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