Maximum Sum Subarray of Size K

The simplest window: its size never changes. There is no rule to check and no shrink loop. Each step, one element enters on the right and one leaves on the left. It is often a warm-up question, and it is where you show you can get the index arithmetic right the first time.

The problem

Given an array of integers and a whole number k, return the largest sum of any k consecutive elements.

• nums = [1, 4, 2, 10, 2, 3, 1], k = 4 → 18. The windows sum to 17, 18, 17 and 16; [4, 2, 10, 2] is the best.
• nums = [1, 12, −5, −6, 50, 3], k = 4 → 51, from [12, −5, −6, 50].

Constraints: 1 ≤ k ≤ n ≤ 10⁵, values between −10⁴ and 10⁴.

Clarifying questions

• Can values be negative? Yes, and it does not matter for a fixed window (see below). It does matter for how you initialise the best.
• Can k be larger than n? Assume not. If it could, ask whether to return 0, None or raise an error.
• Sum or average? Some versions ask for the maximum average. That is the maximum sum divided by k, since k is fixed.
• Return the sum or the window's position? The sum. Returning the start index is a one-line change.

Approach 1: sum every window

Try every start position, add up the k values from there, keep the best.

1def max_sum_of_k_brute(nums: list[int], k: int) -> int:2    """Sum every window from scratch: O(n * k)."""3    best = float("-inf")4    for start in range(len(nums) - k + 1):5        best = max(best, sum(nums[start:start + k]))6    return best

Time: O(n·k). There are n − k + 1 windows and each costs k additions. Space: O(k) for each slice (O(1) if you add with an index loop instead).

Why it is too slow: the cost depends on k. With n = 10⁵ and k = 5 × 10⁴, there are about 5 × 10⁴ windows of 5 × 10⁴ values each: 2.5 × 10⁹ additions. That takes minutes in Python.

The key insight

Two neighbouring windows share almost everything. The window from index 0 to 3 is [1, 4, 2, 10]. The window from 1 to 4 is [4, 2, 10, 2]. They share 4, 2, 10. The brute force adds those three numbers again. It only needs to add the one that entered (2) and subtract the one that left (1):

new_sum = old_sum + entering − leaving = 17 + 2 − 1 = 18

That is two operations per step, whatever k is. The window moves; its summary is repaired, never rebuilt.

Negative numbers are no problem here, and it is worth saying why. Variable windows decide when to shrink based on the sum, and negatives make that decision unreliable. A fixed window never decides anything: it always takes exactly one step. So [1, 12, −5, −6, 50, 3] works as well as all-positive input.

Approach 2: slide the window

1. Sum the first k elements. That is the first window and the first best.
2. For each end from k to n − 1, add nums[end] and subtract nums[end − k].
3. Update the best after each slide.

1def max_sum_of_k(nums: list[int], k: int) -> int:2    """Largest sum of any k consecutive values. Assumes 1 <= k <= len(nums)."""3    window_sum = sum(nums[:k])                    # first window: O(k), once4    best = window_sum5    for end in range(k, len(nums)):6        window_sum += nums[end] - nums[end - k]   # one enters, one leaves7        best = max(best, window_sum)8    return best

Why end − k? After the slide, the window covers indices end − k + 1 to end, which is k elements. The index that was in the window a moment ago and is not now is the one just before the new left edge: end − k. Check it: at end = 4 with k = 4, the leaving index is 0, which holds 1. Correct.

Dry run on [1, 4, 2, 10, 2, 3, 1], k = 4:

The answer is 18. On the second example the sums are 2, then 2 + 50 − 1 = 51, then 51 + 3 − 12 = 42, so the answer is 51 (a best average of 12.75).

Time: O(n): O(k) to build the first window, then O(1) for each of the n − k slides. Space: O(1).

Another route: prefix sums

If you store prefix sums, where prefix[i] is the sum of the first i values, then any window's sum is one subtraction: the window starting at i is prefix[i + k] − prefix[i].

1from itertools import accumulate234def max_sum_of_k_prefix(nums: list[int], k: int) -> int:5    """Window sums from prefix sums: O(n) time, O(n) space."""6    prefix = [0, *accumulate(nums)]      # prefix[i] = sum of nums[:i]7    return max(prefix[i + k] - prefix[i] for i in range(len(nums) - k + 1))

On the example, prefix is [0, 1, 5, 7, 17, 19, 22, 23], and the window sums are 17 − 0, 19 − 1, 22 − 5 and 23 − 7: 17, 18, 17, 16. It is also O(n) time, but it needs O(n) extra space. Prefer it when you must answer many different window sizes or arbitrary ranges from the same array. For one fixed k, the running sum is simpler and uses O(1) space.

Edge cases

• k equals n. The loop does not run; the answer is the sum of the whole array.
• k = 1. Each window is one element; the answer is the largest element.
• All negative values. [−3, −1, −2] with k = 2 gives −3 (from [−1, −2], since [−3, −1] is −4). Starting best at the first window's sum handles this. Starting it at 0 would wrongly return 0.

Follow-ups

• "Return the maximum average." Return best / k. Compare sums, not averages, inside the loop to avoid rounding.
• "Count the windows whose average is at least a threshold." Same slide; instead of max, add one to a counter when window_sum >= threshold * k.
• "Return the maximum of each window, not the sum." A maximum cannot be repaired by adding and subtracting. That needs a monotonic deque; see Sliding Window Maximum.