Greedy Algorithms8 sections · 316 units
Open in Course

Kadane's - Why It Works

The greedy insight

Why does Kadane's algorithm work? The core idea is about negative prefixes.

If the current sum becomes negative, any subarray starting from the current position would be larger without that negative prefix.

So you reset and start fresh. At each position, you decide: extend the current subarray or start a new one here.

You extend if the current sum is positive (it helps).

You reset if it is negative (it hurts).

This local decision leads to the global maximum.