Best total over k consecutive days
nums[i] is the profit on day i, and may be negative. Return the largest total
profit over any k consecutive days.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2,1,5,1,3,2], k = 3 | 9 | Days 2 to 4: 5 + 1 + 3. |
nums = [2,3,4,1,5], k = 2 | 7 | 3 + 4. |
nums = [-3,-1,-4], k = 2 | -4 | Every window loses; the best loses least. |
Constraints
- 1 ≤ k ≤ n ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
Hints
Hint 1
Adding up each window from scratch costs k steps per window. What do two neighbouring windows have in common?
Hint 2
Moving the window one place right adds one element and removes one. Keep the running total.
Hint 3
Start the best at the first window's total, not at 0: every window may be negative.
Where people lose marks
- Initialising the best to 0. With all-negative profits the answer is negative.
- Recording the best before the first window is complete, which compares a partial sum.
- An off-by-one in the element that leaves: when the window ends at i, the element leaving is
nums[i − k].
Dry run on [2,1,5,1,3,2],3
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4nums20lo1152hi133425sum8best8
Build the first window, days 0 to 2: total 8. It is the best so far.
-
Step 2 / 4nums2011lo5213hi3425sum7best8
Slide right: add 1, drop 2. The total is 7; the best stays 8.
-
Step 3 / 4nums201152lo1334hi25sum9best9
Slide right: add 3, drop 1. The total is 9, a new best.
-
Step 4 / 4nums20115213lo3425hisum6best9
Slide right: add 2, drop 5. The total is 6; the best stays 9.
How to think about it
Two neighbouring windows share k − 1 elements. Moving from [i, i + k − 1] to
[i + 1, i + k] adds nums[i + k] and drops nums[i], so the new total
is one addition and one subtraction away from the old. Build the first window in k steps, then slide it
n − k times at constant cost each.
That is the whole of the fixed-size template: some state describing the window (here a sum), an update for the element that enters and one for the element that leaves, and a record of the best state seen. Counts, sets and deques replace the sum in harder problems; the loop stays the same.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def max_sum_k(nums, k):
total = sum(nums[:k]) # the first window
best = total
for i in range(k, len(nums)):
total += nums[i] - nums[i - k] # one in, one out
best = max(best, total)
return best#include <vector>
#include <algorithm>
long long solve(const std::vector<int>& nums, int k) {
long long total = 0;
for (int i = 0; i < k; ++i) total += nums[i]; // the first window
long long best = total;
for (int i = k; i < (int)nums.size(); ++i) {
total += nums[i] - nums[i - k]; // one in, one out
best = std::max(best, total);
}
return best;
}class Solution {
public long maxSumK(int[] nums, int k) {
long total = 0;
for (int i = 0; i < k; i++) total += nums[i]; // the first window
long best = total;
for (int i = k; i < nums.length; i++) {
total += nums[i] - nums[i - k]; // one in, one out
best = Math.max(best, total);
}
return best;
}
}function maxSumK(nums, k) {
let total = 0;
for (let i = 0; i < k; i++) total += nums[i]; // the first window
let best = total;
for (let i = k; i < nums.length; i++) {
total += nums[i] - nums[i - k]; // one in, one out
best = Math.max(best, total);
}
return best;
}fn solve(nums: &[i64], k: usize) -> i64 {
let mut total: i64 = nums[..k].iter().sum(); // the first window
let mut best = total;
for i in k..nums.len() {
total += nums[i] - nums[i - k]; // one in, one out
best = best.max(total);
}
best
}-- Each later window total is the previous one plus the element entering minus the one leaving.
solve :: [Int] -> Int -> Int
solve xs k = maximum (scanl step first (zip (drop k xs) xs))
where
first = sum (take k xs)
step total (new, old) = total + new - old
Variants to try
- Return the starting day as well: remember the index whenever the best improves.
- The best average over k days is the best sum divided by k, so nothing changes.
- Any length of at least k: that is no longer a fixed window; see the prefix-sum approach in the last lesson of this chapter.
Next problems
Most vowels in any k letters
The same fixed window as a running sum, with a count of the letters that matter as its state.
Open the problem → Medium20 minEvery place an anagram begins
Compare a window's letter counts with a pattern's in O(1) per step by tracking how many letters still differ.
Open the problem → Medium15 minDistinct values in every window
Keep a count per value, not a set: a set cannot tell whether the value leaving still has a copy inside.
Open the problem →Write a solution and run it against the real test table.
Keep going
Most vowels in any k letters
The same fixed window as a running sum, with a count of the letters that matter as its state.
Open the problem → Medium20 minEvery place an anagram begins
Compare a window's letter counts with a pattern's in O(1) per step by tracking how many letters still differ.
Open the problem → Medium15 minDistinct values in every window
Keep a count per value, not a set: a set cannot tell whether the value leaving still has a copy inside.
Open the problem → Sliding windowThe pattern behind it
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.