Python programs / Data structures / Sliding window

Python Program to Find the Maximum Sum of K Consecutive Elements

Intermediate Data structures Time O(n) Space O(1)

Finds the largest sum of k items in a row by sliding a window along the list, adding the item that enters and taking away the one that leaves.

A sliding window is a stretch of k items in a row that moves along a list one place at a time. To find the stretch with the largest total, you could add up every window from scratch, but two windows next to each other have k - 1 items in common. So each new total is the old one, plus the item that came in, minus the item that left.

For daily sales of [5, 2, 8, 4, 9, 1, 3, 6] and a window of 3 days, the first window totals 5 + 2 + 8 = 15. Sliding it one place adds 4 and drops 5: 15 + 4 - 5 = 14. The best is 8 + 4 + 9 = 21. The same idea finds the busiest hour in a day of visits or the warmest week in a year of temperatures.

Program

def max_window_sum(items, k):
    """The largest sum of k consecutive items."""
    window = sum(items[i] for i in range(k))
    best = window
    for i in range(k, len(items)):
        # Add the new item, take away the one that left
        window += items[i] - items[i - k]
        best = max(best, window)
    return best


sales = [5, 2, 8, 4, 9, 1, 3, 6]  # one number per day
print("Best 3-day total:", max_window_sum(sales, 3))

Open in the editor Download sliding_window.py

Output

Best 3-day total: 21

How it works

  1. The first window is the first k items, and its total is the best so far. The generator expression adds them up without copying them, as sum(items[:k]) would.
  2. Each pass slides the window one place right. items[i] is the item that comes in on the right, and items[i - k], k places behind it, is the one that drops out on the left. The total changes by the difference, so the window never has to be added up again.
  3. best keeps the largest total seen so far.
  4. After the last window, best is the answer.
  5. The program finds the best 3-day total in eight days of sales.
i Comes in Drops out window best
start 5 + 2 + 8 15 15
3 4 5 14 15
4 9 2 21 21
5 1 8 14 21
6 3 4 13 21
7 6 9 10 21

Time and space complexity

TimeO(n)
Extra spaceO(1)

The first window takes k additions, and each of the other n - k windows takes one addition and one subtraction, so the function is O(n) whatever k is. Adding up every window from scratch takes k additions for each of the n - k + 1 windows, O(n × k): for 1,000 items and a window of 100, that's about 90,000 additions against about 1,900 additions and subtractions here.

The function keeps two totals and an index, so its extra space is O(1). That's why the first window isn't added up with sum(items[:k]): a slice is a new list, a copy of the k items it covers.

Other ways to write it

Adding up every window

The direct way: a total for every place a window can start. It's shorter, but O(n × k).

def max_window_sum(items, k):
    starts = range(len(items) - k + 1)
    return max(sum(items[i:i + k]) for i in starts)

print(max_window_sum([5, 2, 8, 4, 9, 1, 3, 6], 3))

With prefix sums

With the running totals of the list, each window's total is one subtraction. This is O(n) too, but it stores n + 1 totals.

from itertools import accumulate

def max_window_sum(items, k):
    sums = list(accumulate(items, initial=0))
    starts = range(len(items) - k + 1)
    return max(sums[i + k] - sums[i] for i in starts)

print(max_window_sum([5, 2, 8, 4, 9, 1, 3, 6], 3))

Try it yourself

  • Try a window of 1 day (the best single day) and of 8 days (all of them).
  • Find the worst 3-day total instead, with min().
  • Return where the best window starts as well as its total, and print those days: sales[2:5] is [8, 4, 9].
  • Try a window of 10 days, longer than the list: the function fails with an IndexError. Make it raise a ValueError with a clear message instead (errors and exceptions).

More data structures programs

Share this program