AlgoScope

Maximum Sum Subarray of Size k

Slide a fixed window across the array and keep the best sum it ever held.

Sliding window, algorithm, beginner
The largest sum of 3 consecutive values is 12, at indices 4 to 6.active 4-62011521334257617
The largest sum of 3 consecutive values is 12, at indices 4 to 6.active 4-62011521334257617

Sliding Window: Largest sum of 3 in a row

Result, step 7 of 7

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)

Taught by the same lesson

Sliding Window covers these too, in the same run.