Introduction

A moving maximum, also called a sliding-window maximum, asks for the largest value inside every contiguous window of size k. The naive solution recomputes max for every window, but the standard efficient solution uses a deque of indices and runs in linear time.

The Problem

Given:

values = [4, 2, 12, 3, 8, 7, 10]
window_size = 3

The windows are:

• '[4, 2, 12] -> 12'
• '[2, 12, 3] -> 12'
• '[12, 3, 8] -> 12'
• '[3, 8, 7] -> 8'
• '[8, 7, 10] -> 10'

So the moving maximum output is [12, 12, 12, 8, 10].

Naive Solution

The simplest implementation slices each window and calls max:

1def moving_max_naive(values, k):
2    return [max(values[i:i + k]) for i in range(len(values) - k + 1)]
3
4
5print(moving_max_naive([4, 2, 12, 3, 8, 7, 10], 3))

This is easy to read, but it costs O(n * k) time because each window maximum is recomputed from scratch.

Optimal Deque Solution

The linear-time solution keeps a deque of candidate indices. The deque is maintained so that:

• indices stay inside the current window
• values at those indices stay in decreasing order
• the front of the deque always points to the current maximum

1from collections import deque
2
3
4def moving_max(values, k):
5    if k <= 0:
6        raise ValueError("k must be positive")
7    if k > len(values):
8        return []
9
10    dq = deque()
11    result = []
12
13    for i, value in enumerate(values):
14        while dq and dq[0] <= i - k:
15            dq.popleft()
16
17        while dq and values[dq[-1]] <= value:
18            dq.pop()
19
20        dq.append(i)
21
22        if i >= k - 1:
23            result.append(values[dq[0]])
24
25    return result
26
27
28print(moving_max([4, 2, 12, 3, 8, 7, 10], 3))

Each index enters and leaves the deque at most once, which is why the algorithm is O(n).

Why Indices Matter, Especially with Duplicates

The deque should store indices, not values. That detail matters when duplicates exist and when items fall out of the window.

Example:

print(moving_max([5, 5, 3, 5, 2], 2))

If you only store raw values, you lose track of which 5 is leaving the window. Storing indices lets you remove expired elements precisely.

The choice between < and <= in the second while loop also affects duplicate handling. Using <= removes older equal values so the newest equal value survives. That is usually fine because both have the same numeric maximum, and the newer one remains valid for longer future windows.

Streaming Interpretation

This algorithm is valuable because it can be applied to streaming or real-time data. You do not need to recompute the maximum over the entire window after every new point. Instead, you update the deque incrementally as each new value arrives.

That makes it useful for:

• sensor streams
• trading data
• monitoring systems
• rolling anomaly detection

Edge Cases to Handle

A robust implementation should decide what to do for:

• 'k <= 0'
• 'k == 1'
• 'k > len(values)'
• empty input

For example, when k == 1, the answer is simply the original array. When k > len(values), many implementations return an empty result, though some applications may instead want the maximum of the whole array once.

Common Pitfalls

The most common mistake is storing values instead of indices in the deque. That breaks window-expiration logic and becomes especially confusing when duplicate maxima exist.

Another issue is using the wrong comparison when removing smaller elements. If you do not maintain a decreasing deque, the front element is no longer guaranteed to be the maximum.

Finally, be explicit about your window convention. A moving maximum over fixed-size sliding windows is not the same as a cumulative running maximum, and mixing those concepts leads to incorrect tests and confusing outputs.

Summary

• The moving maximum asks for the largest value in every contiguous window of size k.
• The naive approach is simple but costs O(n * k).
• The standard optimal solution uses a deque of indices and runs in O(n).
• Indices are essential for correct duplicate and expiration handling.
• Define edge-case behavior clearly for invalid or oversized windows.