Maximum Sum Subarray of Length K
Maintained by Vikas D, software engineer
You are handed an array of integers and a number k. Your job is to look at every contiguous run of exactly k consecutive elements and report the highest total any of those runs can produce.
A run here means a slice of the array with no gaps. The first valid run covers indices 0 through k-1, the next covers 1 through k, and so on until the window reaches the end of the array. Each of those runs has its own sum.
The array can hold negative numbers, so the answer is not always positive. When every element is negative, the best you can do is the run whose negative total is closest to zero.
Because k is at least 1 and never larger than the array length, at least one valid run always exists, so there is always an answer to return.
Examples
The length-3 runs sum to 8, 7, 9, and 6. The run [5, 1, 3] gives 9, the largest.
Adjacent pairs sum to 5, 7, 5, and 6. The pair [3, 4] reaches 7.
Every pair is negative, summing to -3, -5, and -7. The pair [-1, -2] is the least negative at -3.
Constraints
- 1 <= k <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- k is always a valid window size, so at least one length-k run exists
- The sum fits comfortably in a standard integer, with magnitude at most 10^9
Visible test cases
- maxSumSubarrayK([2,1,5,1,3,2], 3) == 9
- maxSumSubarrayK([2,3,4,1,5], 2) == 7
- maxSumSubarrayK([1,4,2,10,23,3,1,0,20], 4) == 39
- maxSumSubarrayK([-1,-2,-3,-4], 2) == -3
- maxSumSubarrayK([5], 1) == 5
- maxSumSubarrayK([3,3,3,3,3], 5) == 15
Hints
Hint 1
There are exactly nums.length - k + 1 runs to consider. Try writing the most direct loop that scores each one before optimizing.
Hint 2
Two neighboring runs overlap in all but two elements. When the window shifts right by one, only the element that leaves and the element that enters actually change.
Hint 3
Keep a running total. Add the incoming element and subtract the outgoing one each step instead of re-adding the whole window.
Approaches
Brute force over every window
Time O(n * k) · Space O(1)Compute the sum of each length-k run independently and track the maximum.
- Loop the window start from 0 up to nums.length - k.
- For each start, add up the k elements from that start.
- Compare that total against the best seen so far and update it.
- Return the best total after all starts are checked.
Optimal fixed-size sliding window
Time O(n) · Space O(1)Build the sum of the first window once, then slide it across the array, adjusting by only the two elements that change at each step.
- Sum the first k elements and call that the current window sum and the current best.
- Move the window right one position at a time, starting at index k.
- At each step add the entering element nums[i] and subtract the leaving element nums[i - k].
- Update the best whenever the new window sum is larger.
- Return the best after the window reaches the end.
Common mistakes
- Initializing the best answer to 0. With all-negative input, 0 is never achievable and the function would wrongly return 0 instead of the least-negative run.
- Recomputing the full window sum on every shift, which quietly turns the sliding loop back into the O(n * k) brute force.
- Off-by-one errors on the leaving index. The element to subtract is nums[i - k], not nums[i - k - 1] or nums[i - k + 1].
- Handling k equal to nums.length as a special case unnecessarily. The single full-array window is already covered by the first sum.
Follow-up variations
- What if k is not fixed and you must return the maximum sum over all windows whose length is at most k?
- How would you also return the starting index of the best window, not just its sum?
- If the array arrived as a stream and you only kept the last k values, could you still report the running maximum window sum?
- How does the approach change if you need the maximum average of a length-k window instead of the maximum sum?