Sign in to watch this lesson
Algorithms - Arrays · 5:04
Maximum Subarray
The best run of consecutive days in a PnL series, found in one pass. We draw the prefix sums of [-2, 1, -3, 4, -1, 2, 1, -5, 4] as a line, track its lowest point so far and read the answer, 6, as the biggest rise; then run Kadane's algorithm, watch its running sum reset twice, and see why it is the same idea in disguise, measured against checking every segment. We finish with the traps (all-negative arrays, overflow, circular sessions, best trade) and the maximum average over runs of at least L days via binary search on the answer.
You will learn
- Solve maximum subarray in O(n) with prefix sums and a running minimum, recovering exact boundaries
- Implement Kadane's algorithm and explain why resetting a negative running sum is safe
- Avoid the classic traps (all-negative input, overflow) and adapt the loop to best trade and circular sessions
- Find the maximum average over segments of length at least L with binary search on the answer and a prefix-minimum check