Sliding Window (Fixed Size)

A window that slides

Find the biggest total of any k days in a row. Re-adding k numbers for every start is O(n·k). But neighbouring windows share almost everything – add the new item and remove the oldest:

Think of it like this: Looking out of a train window: one new tree appears on the right as one disappears on the left.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v = {2, 1, 5, 1, 3, 2};
    int k = 3;
    long long window = 0;
    for (int i = 0; i < k; i++) window += v[i];
    long long best = window;
    cout << "window 0: " << window << endl;
    for (int r = k; r < (int)v.size(); r++) {
        window += v[r] - v[r - k];      // new item in, oldest out
        best = max(best, window);
        cout << "window " << r - k + 1 << ": " << window << endl;
    }
    cout << "best: " << best << endl;
    return 0;
}

Output

window 0: 8
window 1: 7
window 2: 9
window 3: 6
best: 9

One addition and one subtraction per step: O(n).