The best k days in a row

Given a list of numbers and a size k, find the largest sum of any k consecutive numbers.

Worked example#

For [2, 1, 5, 1, 3, 2] with k = 3:

The best is 9.

The idea#

Adding up each window from scratch means k additions per window, so n times k in total. With a window of a thousand over a hundred thousand numbers that is a hundred million additions for what is really a very simple question.

Look at two neighbouring windows. They share everything except the two ends. Sliding one step to the right means exactly one number joins and exactly one number leaves:

new sum = old sum + nums[right] - nums[left - 1]

So build the first window once, then slide it, doing one addition and one subtraction per step. The work no longer depends on k at all.

This is the whole idea behind a fixed sliding window, and the shape comes back constantly: averages, counts of vowels, how many even numbers are in each window. What changes is what you keep as the window moves. Here it is a running sum, and every one of those updates has to be reversible: whatever adding a number does, removing it has to undo.

Constraints#

• 1 <= k <= n <= 100000
• -10000 <= nums[i] <= 10000