Kadane's Algorithm

Kadane's algorithm finds the best contiguous subarray in one pass. At every index it tracks the best sum of a subarray ending right there, either extending the previous subarray or starting fresh at the current element.

Variant	Running state	Typical use
Reset or extend	Best sum ending here	Maximum subarray sum
Running minimum	Smallest value so far	Best single rise
Two states	Best and worst ending here	Products, where a negative flips them
Prefix minus min prefix	Prefix sum and the smallest prefix seen	Left ends with a constraint

Starting fresh is safe because a negative running sum can only reduce whatever comes after it, so the entire past collapses into one number. That makes Kadane's the smallest dynamic program, with just one state and one transition. You can also view the best sum ending at j as prefix[j+1] minus the smallest earlier prefix, which is the form to use when only certain starting positions are allowed. Maximum non-adjacent sum looks like a Kadane scan but is house robber, which opens 1D Linear DP.

Approach	Time	Extra space
Every subarray, re-summed	$O(n^3)$	$O(1)$
Every pair of prefix sums	$O(n^2)$	$O(n)$
Kadane's	$O(n)$	$O(1)$

Use it when a problem asks for the best contiguous stretch (a sum, a product, or a single rise) and "best ending here" fits in one or two running values.

The problems below start with the classic reset-or-extend scan, move through tracking a running minimum for the best rise and two states for subarray products, and end with the prefix-difference view when endpoints must satisfy a rule.