Kadane's Algorithm

2-minute video explanation

Intuition

You scan numbers from left to right and keep a running sum of a current subarray:

• If your current sum is positive, it’s helping you:
  • Adding the next number can only make things better or at least not worse for a future max.
  • So you keep it and extend the subarray.
• If your current sum becomes negative, it’s hurting you:
  • Any future numbers added on top of this negative sum will be smaller than if you just started fresh from that future number.
  • So you drop it (reset) and start a new subarray at the next position.
    Kadane’s algorithm is literally:

“Keep the current sum while it’s helpful (non-negative).
The moment it turns harmful (negative), throw it away and start over.”
While doing this, you keep track of the best sum you’ve ever seen.

Code example

current_max = nums[0]   # sum of subarray ending here
global_max = nums[0]    # best sum seen so far

for x in nums[1:]:
    # If adding x makes it worse than just x alone, start new at x
    current_max = max(x, current_max + x)

    # Track the best we’ve ever seen
    global_max = max(global_max, current_max)

So:

• current_max = “If I end my subarray here, what’s the best sum I can have?”
• global_max = “Among all positions so far, what’s the best subarray sum I’ve seen?”

Time and Space Complexity

• Time Complexity: $O(n)$ – we scan the array once.
• Space Complexity: $O(1)$ – we use a constant number of variables.