Recompute versus incremental window update
Updated
Recompute walks a[L..R] from scratch after every move (O(window) per move). Incremental folds one include and one exclude into the old state (O(1) per move).
What to focus on
Use incremental for sum and counts. Min/max without a deque often recomputes. If you rescan after every R++, the scan is O(n²), not a sliding window.
Worked examples
sum slide
a = [4, 1, 9, 1], length 3- recompute 4+1+9=14 then 1+9+1=11
- incremental 14-4+1=11
Result: same 11, incremental O(1)
counts slide
s = "abca", length 3- [0,2] {a:1,b:1,c:1}
- drop a add last a → {a:1,b:1,c:1}
- do not rebuild from s[1..3]
Result: one -- and one ++
max without deque
a = [4, 1, 9, 1], length 2- max(4,1)=4
- max(1,9)=9
- max(9,1)=9
- each max walks 2 cells
Result: recompute O(k) here
Try it
Write slideBothWays(a, k). a is an array of integers, or s is a string. k is the window length. The window includes a[L..R]. Incremental updates one include and one exclude. Slide length 3 on [4, 1, 9, 1] both ways and count additions. Slide counts on "abca". Print when max still recomputes. Incremental sum 14-4+1=11 matches recompute.
a (or s) is nonempty. 1 ≤ k ≤ n.