Maintain the sum of the window
Updated
Window sum updates in O(1) per move: add a[R] when R advances, subtract a[L] when L advances. After every move, sum equals a[L]+…+a[R].
What to focus on
Do not rescan a[L..R]. Drop uses the old a[L] before L++. Start from a real [L,R].
Worked examples
expand
a = [4, 1, 9, 1], L=0- R=0 +4 → 4
- R=1 +1 → 5
- R=2 +9 → 14
Result: sum 14 on [0,2]
shrink
a = [4, 1, 9, 1], L=0 R=2, sum 14- drop a[0]=4
- L 0→1
- 14-4=10
Result: sum 10 on [1,2]
slide length 3
a = [4, 1, 9, 1], first [0,2]- 14
- drop 4 add a[3]=1 → 11
Result: sum 11 on [1,3]
Try it
Write windowSum(a). a is an array of integers. L is the left index. R is the right index. The window includes a[L..R]. sum is a[L]+…+a[R]. Expand to R=2, shrink once, then slide length 3. Print sum after each move. Return nothing. On [4, 1, 9, 1] sums are 14, then 10, then 11.
a is nonempty. All values are integers. Start with a real window [L, R].