Example 1
ready- Input
nums = [ 2, 1, 5, 1, 3, 2 ] k = 3- Expected
9- Why
- the window [5, 1, 3] has the largest sum: 9
Maximum Sum Subarray of Size K
25 min · maxSumSubarrayK()easy
A delivery team tracks how many orders arrive each hour. One busy stretch matters more
than the whole day: which run of exactly k hours has the largest total?
Given an integer array nums and an integer k, return the largest sum among all
contiguous subarrays — groups of neighboring elements with no gaps — whose length is
exactly k.
A few ground rules:
- The chosen group must contain exactly
kvalues. You can't skip or reorder values. - Values may be negative. If every possible sum is negative, return the least negative
one rather than
0. - A valid answer can be larger than a signed 32-bit integer, so keep the running sum in
the signature's 64-bit
longresult type.
Constraints
1 <= k <= nums.length <= 100_000-100_000 <= nums[i] <= 100_000
Hints
Write the honest version first
Start at every possible index and add the next k values. It works, but notice how
often neighboring windows add the same values again.
Compare neighboring windows
When a length-k window moves one position right, exactly one value leaves and one
value enters. Everything between them stays in the sum.
Keep one running total
Add the first k values once. For each later position right, add nums[right],
subtract nums[right - k], and update the best sum.
Follow-up
If the values arrived as a stream, could you still find the answer in one pass? What is the smallest amount of recent data you'd need to remember?
Visible cases
Examples
Example 2
ready- Input
nums = [ -8, -3, -6, -2, -5, -4 ] k = 2- Expected
-7- Why
- all windows are negative; [-2, -5] is best at -7
Example 3
ready- Input
nums = [ 4, -1, 2, 10 ] k = 1- Expected
10- Why
- with k = 1, the largest individual value wins
Example 4
ready- Input
nums = [ 5, -2, 3, 4 ] k = 4- Expected
10- Why
- when k equals the array length, the whole array is the only window
Interview signal
Asked at
AmazonGoogle
Recompute every window
For each possible starting position, add the next k values from scratch. Initializing
best from a real window matters: starting at 0 would give the wrong answer when every
window sum is negative.
def max_sum_subarray_k(nums: list[int], k: int) -> int:
best = None
for start in range(len(nums) - k + 1):
window_sum = 0
for i in range(start, start + k):
window_sum += nums[i]
if best is None or window_sum > best:
best = window_sum
return bestTime O(n · k) — there are n - k + 1 windows and each takes k additions.
Space O(1) — the loop keeps only a few numbers.
Fixed sliding window
A sliding window is a fixed-size range that moves across the array while reusing
work from its previous position. Two neighboring length-k windows overlap in k - 1
places. Add the new rightmost value and subtract the old leftmost value instead of
adding the overlap again.
def max_sum_subarray_k(nums: list[int], k: int) -> int:
window_sum = 0
for i in range(k):
window_sum += nums[i]
best = window_sum
for right in range(k, len(nums)):
window_sum += nums[right]
window_sum -= nums[right - k]
best = max(best, window_sum)
return bestAfter each update, window_sum is exactly the sum from right - k + 1 through right.
That invariant covers every valid window once, so the largest value recorded in best
is the answer.
Time O(n) — the first window is added once, then each remaining value enters and one value leaves. Space O(1) — no extra array grows with the input.
The sum can reach 10_000_000_000, so languages with fixed-width integers need a 64-bit
running total as well as a 64-bit return value.
Loading editor
Console
ready to runReady to run.
4 cases are queued.
Visible testcase
Case 1
Expected
9
Run: visible + custom · Submit: full suite