Fixed Window Max Sum
Largest sum of k consecutive elements. Instead of re-summing each window, add the new element and subtract the one that slid out — a running sum in O(n).
- Category
- Sliding Window
- Time complexity
- O(n)
- Space complexity
- O(1)
Pseudocode
sum the first k elements slide: sum += a[i] − a[i−k] track the best window sum return the maximum
Reference implementation
sum = sum(a[:k]); best = sum
for i in range(k, n):
sum += a[i] - a[i-k]
best = max(best, sum)