Sliding Window Array

A sliding window tracks a contiguous subarray while moving its boundaries through the array. Instead of recomputing each subarray from scratch, it updates the current state when elements enter or leave the window.

You use it when the problem asks about contiguous ranges, especially fixed-size windows or variable-size windows with a constraint.

Problem

Given an array $A$ of length $n$ and a window size $k$, find the maximum sum of any contiguous subarray of length $k$.

The window covers indices:

where:

Algorithm

First compute the sum of the first window. Then move the window one position at a time by subtracting the element that leaves and adding the element that enters.

max_window_sum(A, k):
    n = length(A)

    current = 0
    for i from 0 to k - 1:
        current += A[i]

    best = current

    for r from k to n - 1:
        current -= A[r - k]
        current += A[r]
        best = max(best, current)

    return best

Example

Let

and

Return $16$.

Correctness

The first loop computes the sum of the initial window $A[0:k]$. Each later step removes exactly the element that leaves the window and adds exactly the element that enters the window. Therefore, current always equals the sum of the active window.

The algorithm compares every length-$k$ window once, so best stores the maximum window sum.

Complexity

Space usage:

When to Use

Sliding windows are appropriate when:

• the answer depends on contiguous subarrays
• each step can update state incrementally
• the window has fixed size
• the window can grow or shrink under a constraint

They are less suitable when ranges are arbitrary and many independent queries are required. In that case, use prefix sums, Fenwick trees, or segment trees.

Implementation

def max_window_sum(a, k):
    if k <= 0 or k > len(a):
        raise ValueError("invalid window size")

    current = sum(a[:k])
    best = current

    for r in range(k, len(a)):
        current -= a[r - k]
        current += a[r]
        best = max(best, current)

    return best

func MaxWindowSum(a []int, k int) (int, bool) {
    if k <= 0 || k > len(a) {
        return 0, false
    }

    current := 0
    for i := 0; i < k; i++ {
        current += a[i]
    }

    best := current

    for r := k; r < len(a); r++ {
        current -= a[r-k]
        current += a[r]
        if current > best {
            best = current
        }
    }

    return best, true
}