Description

Kadane's finds the maximum-sum contiguous subarray in one pass. At each element you decide: extend the current run, or start fresh from here.
?

Reach for when

You want the maximum (or minimum) sum of a contiguous subarray.

Runtime

O(n) time, O(1) space

Visualization

Pseudocode

best = cur = arr[0]
for x in arr[1:]:
	cur = max(x, cur + x)     # extend the run, or restart at x
	best = max(best, cur)
return best

Code

def max_subarray(nums):
	best = cur = nums[0]
	for x in nums[1:]:
		cur = max(x, cur + x)     # extend the run, or start fresh at x
		best = max(best, cur)
	return best