AlgoScope

Maximum Subarray

The largest total of any run of neighbours. Kadane solves it in one pass.

Array algorithms and techniques, algorithm, intermediate
The maximum subarray sum is 6, at indices 3 to 6.active 3-6-2011-3243-142516-5748
The maximum subarray sum is 6, at indices 3 to 6.active 3-6-2011-3243-142516-5748

Prefix Sum and Kadane: Kadane on a mixed array

Result, step 10 of 10

The best run is indices 3 to 6 with total 6. One pass, one carried number, O(n).

How prefix sum and kadane works

Cost

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

Divide and conquer variant is O(n log n).

Taught by the same lesson

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