Maximum Sum Subarray of Size K
EasyFixed window · add one, drop one
Slide a window of k numbers along, adding the new one and dropping the old one instead of re-adding every time.
The idea
Keep a window of exactly k elements. Slide it by adding the new right element and subtracting the one that fell off the left — O(1) per step instead of re-summing.
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.
1for (let i = 0; i + k <= n; i++) {2 let sum = 0;3 for (let j = i; j < i + k; j++) sum += nums[j];4 best = Math.max(best, sum);5}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.