AlgoScope

Kadane's Algorithm

Carry the best run ending here. A negative run only hurts, so drop it and start over.

Array algorithms and techniques, algorithm, intermediateAlso called maximum subarray
At index 1 the best run ending here is 1. That is the new overall best.active 1-1-2011-3243-142516-5748i
At index 1 the best run ending here is 1. That is the new overall best.active 1-1-2011-3243-142516-5748i

Prefix Sum and Kadane: Kadane on a mixed array

Decision, step 2 of 10

The run so far totals -2, and dragging that along would only hurt. Start over at 1. That is a new best.

How prefix sum and kadane works

Cost

Best
O(n)
Average
O(n)
Worst
O(n)
Space
O(1)

Leads to

Topics that need this one first.

Taught by the same lesson

Prefix Sum and Kadane covers these too, in the same run.