Sliding window: max sum of k

Find the largest sum of any k consecutive elements without re-adding the whole window each time.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

When the window slides one step, only two elements change: one enters on the right and one leaves on the left. Update the sum with those two values instead of recomputing it.

Code

C++PythonC#

int maxWindowSum(const vector<int>& a, int k) {
    int window = 0;
    for (int i = 0; i < k; i++) window += a[i];
    int best = window;
    for (int r = k; r < (int)a.size(); r++) {
        window += a[r] - a[r - k];
        best = max(best, window);
    }
    return best;
}

def max_window_sum(a: list[int], k: int) -> int:
    window = sum(a[:k])
    best = window
    for r in range(k, len(a)):
        window += a[r] - a[r - k]
        best = max(best, window)
    return best

public static int MaxWindowSum(int[] a, int k) {
    int window = 0;
    for (int i = 0; i < k; i++) window += a[i];
    int best = window;
    for (int r = k; r < a.Length; r++) {
        window += a[r] - a[r - k];
        best = Math.Max(best, window);
    }
    return best;
}

Tips

Fixed-size windows add one and drop one each step.
Variable-size windows grow on the right and shrink on the left while a condition holds. See the Strings section.

In the .NET library

a.Skip(i).Take(k).Sum() in a loop is the O(n·k) version this replaces. Fine for small inputs, slow for large ones.