041. Maximum Fixed-Window Sum

Why this mechanism works

Consecutive size-k windows differ by one departing and one arriving value. Update the sum with that difference instead of summing k cells again. Seed the best answer from an actual window, because zero may exceed every legal negative window sum.

State and boundaries

total is the current size-k window sum. best is the maximum sum among complete windows processed so far.

Protocol

1. Reject an invalid window size.
2. Sum the first k values.
3. Move the right endpoint forward.
4. Add the incoming value and subtract the departing value.
5. Compare the repaired sum with best.

Visualization

[2,1,5] 1 3 2 -> sum 8
2 [1,5,1] 3 2 -> 8 - 2 + 1 = 7
2 1 [5,1,3] 2 -> 7 - 1 + 3 = 9

Python implementation

def max_window_sum(nums, k):
    if k < 1 or k > len(nums):
        return None
    total = sum(nums[:k])
    best = total
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]
        best = max(best, total)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 max_window_sum: if k < 1 or k > len(nums):
nums=[2, 1, 5, 1, 3, 2]; k=3

L4 max_window_sum: total = sum(nums[:k])
nums=[2, 1, 5, 1, 3, 2]; k=3; total=8

L5 max_window_sum: best = total
nums=[2, 1, 5, 1, 3, 2]; k=3; total=8; best=8

L6 max_window_sum: for right in range(k, len(nums)):
nums=[2, 1, 5, 1, 3, 2]; k=3; total=8; best=8; right=3

L7 max_window_sum: total += nums[right] - nums[right - k]
nums=[2, 1, 5, 1, 3, 2]; k=3; total=7; best=8; right=3

L6 max_window_sum: for right in range(k, len(nums)):
nums=[2, 1, 5, 1, 3, 2]; k=3; total=7; best=8; right=4

L7 max_window_sum: total += nums[right] - nums[right - k]
nums=[2, 1, 5, 1, 3, 2]; k=3; total=9; best=8; right=4

L8 max_window_sum: best = max(best, total)
nums=[2, 1, 5, 1, 3, 2]; k=3; total=9; best=9; right=4

L6 max_window_sum: for right in range(k, len(nums)):
nums=[2, 1, 5, 1, 3, 2]; k=3; total=9; best=9; right=5

L7 max_window_sum: total += nums[right] - nums[right - k]
nums=[2, 1, 5, 1, 3, 2]; k=3; total=6; best=9; right=5

L2 max_window_sum: if k < 1 or k > len(nums):
nums=[-5, -2, -3]; k=2

L4 max_window_sum: total = sum(nums[:k])
nums=[-5, -2, -3]; k=2; total=-7

L5 max_window_sum: best = total
nums=[-5, -2, -3]; k=2; total=-7; best=-7

L6 max_window_sum: for right in range(k, len(nums)):
nums=[-5, -2, -3]; k=2; total=-7; best=-7; right=2

L7 max_window_sum: total += nums[right] - nums[right - k]
nums=[-5, -2, -3]; k=2; total=-5; best=-7; right=2

L8 max_window_sum: best = max(best, total)
nums=[-5, -2, -3]; k=2; total=-5; best=-5; right=2

Why the solution is correct

The initial sum represents the first window. Each replacement removes exactly the value leaving the window and adds exactly the entering value, preserving its size and sum. Every complete window is visited once, so the maximum is correct.

Time and space

O(n) time; O(k) temporary space from the initial slice in this implementation, with O(1) persistent state.

Common mistakes

Initializing best to zero fails for negative sums. Subtracting nums[right-k+1] removes the wrong departing value.

Reasoning card

Transfer exercise

Remove the initial slice allocation while keeping the same recurrence and O(n) time.