Maximum Subarray Sum of Size K

Difficulty: Easy

Problem

Given an array of positive integers and a positive integer k, find the maximum sum of any contiguous subarray of size k.

Example

Input: nums = [2, 1, 5, 1, 3, 2], k = 3
Output: 9
Explanation: Subarray [5, 1, 3] has the maximum sum of 9 among all subarrays of size 3.

Brute-force approach

For each starting position, sum k elements and track the maximum.

Steps

  1. For each starting index i from 0 to n-k
  2. Sum k elements starting from i
  3. Update maxSum if current sum is larger
  4. Return maxSum

Time complexity: O(n * k) · Space complexity: O(1)

Trade-offs

  • Re-sums k elements for every window — adjacent windows share k-1 elements!
  • For [2,1,5] → [1,5,1]: we re-added 1 and 5 even though they were already summed
  • Can we reuse the previous sum and just add/remove one element?

Optimal approach

Key insight: When sliding from one window to the next, the sum changes by exactly: +new_right - old_left. No need to re-sum k elements!

Use a fixed-size sliding window: add right element, subtract left element.

Steps

  1. Sum the first k elements (initial window)
  2. Set maxSum = initial window sum
  3. For each position from k to n-1: slide window
  4. windowSum = windowSum - nums[i-k] + nums[i]
  5. Update maxSum if windowSum is larger

Time complexity: O(n) · Space complexity: O(1)