Maximum Sum Subarray of Size k
Slide a fixed window across the array and keep the best sum it ever held.
Sliding Window: Largest sum of 3 in a row
The best window is indices 4 to 6 with sum 12. 5 slides, each O(1), so O(n) overall.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
Taught by the same lesson
Sliding Window covers these too, in the same run.