Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

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).

easyPattern: Sliding Window

Updated Quick read: 3 min read

Approaches at a glance

ApproachTimeSpace
Brute forceO(n·k)O(1)
Sliding windowO(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 best

There 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 = 6

Add 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 best

When 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)); // 7

Python

print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # 9
print(max_sum_subarray([2, 3, 4, 1, 5], 2))  # 7

The comment after each line is the result you should see.

Common mistakes

  • Starting best at 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], not numbers[i - k + 1].
  • Not handling k larger than the array. No window of that size exists. Decide what to return, here null, and check for it first.