Maximum Subarray
The largest total of any run of neighbours. Kadane solves it in one pass.
Prefix Sum and Kadane: Kadane on a mixed array
The best run is indices 3 to 6 with total 6. One pass, one carried number, O(n).
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Divide and conquer variant is O(n log n).
Before this
Related
Taught by the same lesson
Prefix Sum and Kadane covers these too, in the same run.