Free Arrays lessonsArrays · Stage 8 · Sliding window · Step 1

Slide, don't re-add

Move a fixed-size window one step at a time, adding one number and dropping one. About 8 minutes.

Neighbouring windows share almost everything

You want the best total of any 3 days in a row of sales. Adding up every group of 3 from scratch repeats a lot of work: two neighbouring groups share 2 of their 3 days.

So don't start over. When the window slides one day to the right, add the day coming in and subtract the day going out. The new total takes one step, whatever the size of the window.

New total: the old total, plus the day coming in, minus the day going out.

Build the first window, then slide

Add up the first window once, the slow way. Then slide it along one box at a time, updating the total and comparing it with the best so far.

The day leaving the window is always exactly the window's size behind the day entering it. Get that distance right and the rest is easy.

First window: add it up once.

The one leaving: is exactly one window-length behind.

In code

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

k = 3

leftright

First window: 2 + 1 + 5 = 8. Best 8.

Move 1 of 4

Quick check

The window of 2 holds 4 and 7, a total of 11. The next number is 1. What's the next window's total?

Show the answer

8. 11 + 1 − 4 = 8: the total of 7 and 1.

Your problem

Best window of k

You get a list of numbers and a size k. Among all runs of exactly k consecutive numbers, return the largest sum.

Example

nums = [2, 1, 5, 1, 3, 2], k = 3 → 9

1 ≤ k ≤ n ≤ 1,000,000 · −10^6 ≤ each value ≤ 10^6 · return a long

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.