The challenge
Return the largest sum among all contiguous subarrays of exactly k elements.
Use 1 ≤ k ≤ n. Values may be negative. Indices are zero-based.
Example
[2, 1, 5, 1, 3, 2], k = 3 → 9, from [5, 1, 3].
Use the walkthrough below to inspect the input and each state change.
See Fixed-size sum, step by step
Expand, shrink, and inspect the window state.
6 elements · zero-based indicesk = 3
Current windowRecorded answerOutside window
- Left
- 0
- Right
- -1
- Length
- 0
Step 01 / 12
Start with an empty window
Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.
left = 0; right = −1Answer so far
0
View exact input
Input: [2,1,5,1,3,2] · k = 3
Current window is empty.
Put it into code
Build the first sum once. Each slide adds one value and removes one value. Divide the best sum by k to get the maximum fixed-window average.
Indices are zero-based. C++ uses C++17 or later.
def max_window_sum(nums, k):
# Contract: 1 <= k <= len(nums).
total = sum(nums[:k])
best = total # Correct even when every value is negative.
for right in range(k, len(nums)):
total += nums[right] - nums[right - k]
best = max(best, total)
return best#include <algorithm>
#include <array>
#include <deque>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
long long max_window_sum(const vector<int>& nums, int k) {
// Contract: 1 <= k <= nums.size().
long long total = 0;
for (int i = 0; i < k; ++i) total += nums[i];
long long best = total;
for (int r = k; r < (int)nums.size(); ++r) {
total += (long long)nums[r] - nums[r - k];
best = max(best, total);
}
return best;
}