Maximum Sum of k Consecutive Elements (Sliding Window)
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.
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;
}