Maximum Sum Subarray of Size K
Find the largest sum of any k consecutive elements in an array using a fixed-size sliding window, in O(n) time instead of O(n·k).
Updated Quick read: 3 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n·k) | O(1) |
| Sliding window | O(n) | O(1) |
The problem
Given an array of numbers and a whole number k, find the largest sum of any k consecutive elements.
numbers = [2, 1, 5, 1, 3, 2], k = 3 → 9 (5 + 1 + 3)
numbers = [2, 3, 4, 1, 5], k = 2 → 7 (3 + 4)Approach 1: brute force
For every possible starting position, add up the next k elements.
JavaScript
function maxSumSubarrayBruteForce(numbers, k) {
if (k <= 0 || k > numbers.length) return null;
let best = -Infinity;
for (let start = 0; start + k <= numbers.length; start++) {
let sum = 0;
for (let i = start; i < start + k; i++) {
sum += numbers[i];
}
best = Math.max(best, sum);
}
return best;
}Python
def max_sum_subarray_brute_force(numbers, k):
if k <= 0 or k > len(numbers):
return None
best = float("-inf")
for start in range(len(numbers) - k + 1):
total = 0
for i in range(start, start + k):
total += numbers[i]
best = max(best, total)
return bestThere are about n starting positions and each costs k additions.
Time O(n·k). Space O(1).
Approach 2: sliding window
Neighbouring groups overlap almost completely. Moving from one group to the next drops one element at the left and gains one at the right; the k - 1 elements in between are unchanged. So there is no need to add them up again.
[ 2 1 5 ] 1 3 2 sum = 8
2 [ 1 5 1 ] 3 2 sum = 8 - 2 + 1 = 7
2 1 [ 5 1 3 ] 2 sum = 7 - 1 + 3 = 9
2 1 5 [ 1 3 2 ] sum = 9 - 5 + 2 = 6Add up the first k elements once. Then slide: add the element that enters, subtract the one that leaves.
JavaScript
function maxSumSubarray(numbers, k) {
if (k <= 0 || k > numbers.length) return null;
let windowSum = 0;
for (let i = 0; i < k; i++) {
windowSum += numbers[i];
}
let best = windowSum;
for (let i = k; i < numbers.length; i++) {
windowSum += numbers[i] - numbers[i - k];
best = Math.max(best, windowSum);
}
return best;
}Python
def max_sum_subarray(numbers, k):
if k <= 0 or k > len(numbers):
return None
window_sum = sum(numbers[:k])
best = window_sum
for i in range(k, len(numbers)):
window_sum += numbers[i] - numbers[i - k]
best = max(best, window_sum)
return bestWhen the element at index i enters, the window covers indexes i - k + 1 to i, so the element that leaves is the one at i - k.
Time O(n): each element is added once and subtracted at most once, whatever k is. Space O(1).
This is the fixed-size form of the sliding window pattern.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9
console.log(maxSumSubarray([2, 3, 4, 1, 5], 2)); // 7Python
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3)) # 9
print(max_sum_subarray([2, 3, 4, 1, 5], 2)) # 7The comment after each line is the result you should see.
Common mistakes
- Starting
bestat 0. If every number is negative, the true answer is negative and 0 would be wrong. Start from the first window's sum. - Subtracting the wrong element. The element leaving is
numbers[i - k], notnumbers[i - k + 1]. - Not handling
klarger than the array. No window of that size exists. Decide what to return, herenull, and check for it first.