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. Here is my attempt to make this explanation more easy to digest.