Return the maximum sum of any contiguous subarray of exactly length k. Assume
1 <= k <= len(nums).
maxSubarraySum(nums, k)
Input format: nums | k.
[1, 2, 3, 4], k=2 // → 7 (3+4)
[4, 2, 1, 6], k=1 // → 6
[-1, -2, -3], k=2 // → -3 (-1 + -2)
You need the largest sum among all contiguous stretches of exactly k elements. The brute-force instinct: for every starting position, sum the next k elements and keep the best. For a list of length n, that's roughly n windows at O(k) each — O(n·k) total, degrading toward O(n²) when k is large.
Look at two neighboring windows: the one starting at i and the one starting at i+1 overlap in k-1 elements — nearly everything. The brute-force approach throws away the sum it just computed and re-adds all those shared elements from scratch.
Instead of recomputing each window's sum, maintain one running sum and update it as the window slides. Moving right by one changes exactly two things: one element joins on the right, one falls off the left. Everything else is unchanged. So: new sum = old sum + incoming element − outgoing element. Constant work per slide, regardless of k.
Since the window size is fixed, there's no ambiguity about which element leaves — always the one exactly k positions behind the newcomer. That makes each update O(1) instead of O(k), so the whole scan is O(n) instead of O(n·k). You only remember the current sum and the best sum — not the window's contents — so it's O(1) extra space too.
"Add what enters, subtract what leaves" is the core idea behind every fixed-size sliding window problem: whenever consecutive windows overlap heavily, look for an incremental update instead of recomputing from scratch.
def max_subarray_sum(nums, k):
total = sum(nums[:k])
best = total
for right in range(k, len(nums)):
total += nums[right] - nums[right - k]
if total > best:
best = total
return best
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.