Kadane's Algorithm

Spotting one

You want the best unbroken run inside a list. Biggest total, biggest product. And the values can be negative.

Unbroken is the important word. If you are allowed to pick and choose items freely, this is not the method.

Kadane or sliding window?

This is the distinction worth getting straight, and the sliding window page covers the other half of it.

Sliding window leans on an assumption: once a stretch goes bad, making it longer cannot rescue it. True when everything is positive. False the moment a negative appears, because a negative can pull a bad total back into a good one. When negatives are in play, Kadane is the tool.

Where to start

Maximum Subarray is the plain form. Everything else here is a variation on it.

Maximum Product Subarray next, and it teaches the most useful lesson on this page. You have to track the smallest running product as well as the largest, because a big negative multiplied by another negative becomes the new winner.

Maximum Sum Circular Subarray adds a tidy trick: the best run that wraps around the end is everything except the worst run in the middle.

Maximum Absolute Sum of Any Subarray and Maximum Subarray Sum with One Deletion build from there.

Common mistakes

Starting the best-so-far at zero. If every number is negative the answer is the least bad single number, and starting at zero reports zero, which is not a run at all.

On the product version, tracking only the maximum and then being surprised when two negatives beat it.