</>EmbeddedInterview

How do you find the maximum sum of k consecutive elements (sliding window)?

MediumArrays & Strings (Coding Round)

Short answer: Sum the first k elements; that is the first window and the first candidate for the maximum. Then slide: add the element entering the window and subtract the one leaving (sum += a[i] - a[i-k]), updating the maximum each time. O(n) instead of O(n·k).

#include <stddef.h>

/* 1 <= k <= n */
long max_window_sum(const int *a, size_t n, size_t k)
{
    long sum = 0;
    for (size_t i = 0; i < k; i++)
        sum += a[i];
    long best = sum;                       /* the first window counts too */
    for (size_t i = k; i < n; i++) {
        sum += a[i] - a[i - k];
        if (sum > best) best = sum;
    }
    return best;
}
/* {1, 8, 30, -5, 20, 7}, k = 3 -> 45  (30 - 5 + 20) */

Dry run (k = 3): first window 1+8+30 = 39 (best 39). Slide: +(-5) -1 = 33. +20 -8 = 45 (best 45). +7 -30 = 22. Answer 45.

The bug to avoid. Initialising maxSum = 0 and only comparing inside the sliding loop has two problems: the first window is never considered (wrong if it is the biggest), and if every window sum is negative the function returns 0. Set best to the first window's sum.

Overflow: the running sum of many int values can overflow; use a wider accumulator (long or int64_t).

Embedded uses of the same idea

  • Moving-average filter: keep a ring buffer of the last k samples and a running sum; each new sample adds one value and subtracts the oldest. Dividing by k gives the average. With k a power of two, the division is a shift.
  • Rate limiting: count events in the last k milliseconds.

Follow-ups: variable-size window ("smallest subarray with sum ≥ S": grow the right edge, shrink the left edge while the condition holds), and "maximum in every window of size k" (deque of indices, O(n)).