mycsmajor
Data structures problem 12 of 30

Best window sum

  • Data structures
  • Easy

Write max_window_sum(nums, k) that returns the largest sum of any k consecutive items. Assume 1 ≤ k ≤ len(nums). Aim for O(n).

max_window_sum([2, 1, 5, 1, 3, 2], 3)   # 9  (5 + 1 + 3)
Show hint

When the window slides one step right, one item enters and one item leaves. You do not need to add up the whole window again.

Show solution 
def max_window_sum(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

Re-summing every window would be O(n · k). The sliding window updates the sum in O(1) per step, so the whole thing is O(n). Sliding windows solve a whole family of "best consecutive stretch" problems.

Want a problem like this every day? See today's problem and keep a streak going.