Advanced · Techniques · 208 of 264
Best k days in a row
Find the largest total of k numbers next to each other. Slide a window: add the number entering and subtract the one leaving instead of re-adding k numbers.
Input: whole numbers on one line, then k. Output: the largest window sum.
Examples
Input
1 4 2 10 2 3 1 0 20 4
Output
24
Input
5 1
Output
5
Input
-1 -2 -3 2
Output
-3
One more test checks other inputs when you press Check.
Stuck? The idea behind techniques
Some problems have a known shape. Two pointers move from both ends of a sorted list. A sliding window keeps a running total as it moves, adding one item and taking one away.
A dictionary of what has been seen turns a search inside a loop into a single lookup.
nums = [2, 7, 11, 15]
target = 9
seen = {}
for i, x in enumerate(nums):
if target - x in seen:
print(seen[target - x], i)
seen[x] = iWatch for: A loop inside a loop over the same long list is slow: the hidden tests may use big inputs.