Sliding Window
Loading
Loading
Sliding Window
Add one, drop one: the cheapest possible slide.
By the end of this chapter
def best_window(nums, k): total = sum(nums[:k]) best = total for right in range(k, len(nums)): total += nums[right] - nums[right - k] # in on the right, out on the left best = max(best, total) return bestnums = [2, 1, 5, 1], k = 3[2,1,5]1total 82[1,5,1]+1 -2 → total 7best = 8A sum can be undone by subtracting. A maximum cannot — once the largest element leaves, you have no idea what the next largest was. That needs a monotonic deque, covered in the queues section.
Sign in to keep a note here. It is free, and nobody else can see it.
Sign inWhat this chapter was for:
Before moving on: try 2 practice problems.