Maximum sum of k days
We'll cover the following
Given daily sales and a number k, find the biggest total of any k days in a row.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
L/R10
11
92
73
54
45
56
37
58
79
310
211
712
513
214
415
316
517
Add 1. Still filling the first window.
sum 1
1 / 19
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | Each day enters and leaves the window once. |
In Python
def best_k(nums, k):
cur = sum(nums[:k]); best = cur
for r in range(k, len(nums)):
cur += nums[r] - nums[r - k] # add new, drop old
best = max(best, cur)
return bestSummary: say it in the interview
- The window always has k items. Moving right adds one item and removes one. Update the sum instead of re-adding k numbers every time.
- Time O(n), space O(1). Each day enters and leaves the window once.