Max Sum Subarray of Size K
MediumSlide a fixed window, add one and drop one
Problem
Return the maximum sum of any contiguous subarray of size k.
Slide a fixed window of size k, adding the new element and dropping the old one each step.
The idea
Sum the first k elements, then move the window along by adding the entering element and subtracting the leaving one. Recomputing each window from scratch would be O(n·k); the add-and-drop update makes it O(n).
The trick
- Build the first window separately, then slide.
- Each step is two arithmetic operations, whatever the size of k.
2
1
5
1
3
2
0
1
2
3
4
5
k3
Step 1 of 6. Brute force: re-add each window of size 3 from scratch. Values: 2, 1, 5, 1, 3, 2. k 3.
1/6
Brute force
timeO(n·k)spaceO(1)
Re-add each window.
1// re-add each window of size k from scratch2for (let i = 0; i + k <= n; i++) {3 let sum = 0;4 for (let j = i; j < i + k; j++) sum += nums[j];5 best = Math.max(best, sum);6}Input
- array
- [2, 1, 5, 1, 3, 2]
Memory
- k
- 3
Output
- best
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 1, 5, 1, 3, 2], k = 3
- Output:
- 9
- Explanation:
- [5,1,3] gives the biggest window sum, 9.
Example 2
- Input:
- nums = [1, 2, 3, 4], k = 2
- Output:
- 7
- Explanation:
- [3,4] sums to 7.
Example 3
- Input:
- nums = [5], k = 1
- Output:
- 5
- Explanation:
- A single-element window.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.