0

Sliding window: fixed size

Patternsused in ~95% of apps

You need the best block of k in a row. Recomputing each block from scratch is the obvious answer and it is far too slow. Sliding the window instead, add one, drop one, turns the same job into a single pass.

Core idea. Compute the first window the slow way, once. After that, move it one step at a time: add the value entering on the right, subtract the value leaving on the left. Each move costs one addition and one subtraction, not k of them.
Playground, this isn't a screenshot
best sum of 3 in a row, [2, 1, 5, 1, 3, 2]
2
1
5
1
3
2
= 8first window, added the slow waybest 8
2
1
5
1
3
2
= 7+1 entering, −2 leavingbest 8
2
1
5
1
3
2
= 9+3 entering, −1 leavingbest 9
2
1
5
1
3
2
= 6+2 entering, −5 leavingbest 9

Four windows, but only one full addition. Every later window cost two operations instead of three.

↑ play a little first, then dig in