</>EmbeddedInterview
← All problems · Arrays & Searching

Maximum Sum of k Consecutive Elements (Sliding Window)

Easy

Implement bool max_window_sum(const int *a, size_t n, size_t k, long *out) that finds the largest sum of any k consecutive elements and writes it to *out. Return false if k is 0 or larger than n. Run in O(n) time.

Example: {2, 1, 5, 1, 3, 2}, k = 3 → 9 (5 + 1 + 3).

This is the same idea as a moving-average filter on sensor samples.

Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.

Compute the sum of the first k elements once. Each time the window moves right by one, add the element entering and subtract the element leaving. Do not start max at 0: the array may be all negative.

#include <stdio.h>
#include <stdbool.h>
#include <stddef.h>

bool max_window_sum(const int *a, size_t n, size_t k, long *out)
{
    if (k == 0 || k > n) return false;

    long long sum = 0;
    for (size_t i = 0; i < k; i++)        /* first window */
        sum += a[i];

    long long best = sum;
    for (size_t i = k; i < n; i++) {
        sum += a[i] - (long long)a[i - k];  /* slide: add new, drop old */
        if (sum > best) best = sum;
    }
    *out = (long)best;
    return true;
}

Re-adding all k elements for every window costs O(n·k). The sliding window reuses the previous sum, so each step is two additions: O(n) time, O(1) memory.

Walk-through: {2, 1, 5, 1, 3, 2}, k = 3

window operation sum best
[2 1 5] initial 8 8
[1 5 1] +1 −2 7 8
[5 1 3] +3 −1 9 9
[1 3 2] +2 −5 6 9

Edge cases: k == 0 or k > n (the original version silently returned 0, which is also a valid sum, so a separate status is clearer); all-negative input (initialise best from the first window, never 0); overflow (two large ints overflow int, so accumulate in a 64-bit type).

Follow-ups: the variable-size window (shortest subarray with sum ≥ S, longest substring without repeating characters) grows the right edge and shrinks the left edge; the maximum of each window uses a deque for O(n). In firmware the same structure is a moving-average filter over a ring buffer.

solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
    long s = 0;
    const int a[] = { 2, 1, 5, 1, 3, 2 };
    CHECK(max_window_sum(a, 6, 3, &s) && s == 9);
    CHECK(max_window_sum(a, 6, 1, &s) && s == 5);
    CHECK(max_window_sum(a, 6, 6, &s) && s == 14);
    const int neg[] = { -4, -2, -7, -1 };
    CHECK(max_window_sum(neg, 4, 2, &s) && s == -6);      /* all negative */
    const int big[] = { 2000000000, 2000000000, 1 };
    CHECK(max_window_sum(big, 3, 2, &s) && s == 4000000000L);
    CHECK(!max_window_sum(a, 6, 0, &s));
    CHECK(!max_window_sum(a, 6, 7, &s));
    puts(fails ? "Some tests failed" : "All tests passed");
    return fails != 0;
}