Maximum Sum Subarray of Size K

Problem

You are given an array of integers nums and a positive integer k. Your task is to find the maximum sum of any contiguous subarray of exactly size k.

This is a classic problem that tests your ability to optimize a brute-force O(n·k) solution into an efficient O(n) sliding window approach.

Input Format

• nums: a list of integers
• k: a positive integer representing the subarray size

Output Format

Return a single integer representing the maximum sum among all subarrays of size k.

Examples

Example 1

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: The subarray [5, 1, 3] has the maximum sum of 9. Other subarrays of size 3: [2,1,5]=8, [1,3,2]=6.

Example 2

Input: nums = [1, 4, 2, 10, 23, 3, 1, 0, 20], k = 4
Output: 39
Explanation: The subarray [4, 2, 10, 23] sums to 39, which is the maximum among all windows of size 4.

Example 3

Input: nums = [-1, -2, -3, -4], k = 2
Output: -3
Explanation: All elements are negative. The subarray [-1, -2] has the maximum sum of -3.

Approach Hints

Brute Force (O(n·k)): For every starting index i from 0 to n-k, compute the sum of the subarray nums[i..i+k-1] and track the maximum. This works but is inefficient for large inputs.

Sliding Window (O(n)):

1. Compute the sum of the first k elements — this is your initial window.
2. Slide the window one element at a time: add the incoming element on the right and subtract the outgoing element on the left.
3. At each step, update the maximum sum seen so far.
4. Return the maximum after processing all windows.

The key insight: instead of recomputing the sum from scratch for each window, you reuse the previous window's sum in O(1) time.

Function Signature

def max_sum_subarray(nums: list[int], k: int) -> :