Sliding window: suma maximă a k elemente în C++

Dacă lungimea secvenței este fixă, nu trebuie să recalculezi fiecare sumă de la zero. La trecerea la următoarea secvență, elimini valoarea care iese pe stânga și adaugi valoarea care intră pe dreapta. Aceasta este tehnica ferestrei glisante, numită și sliding window.

Ce calculăm

Citim 1 ≤ k ≤ n ≤ 1000 și n valori întregi cu modulul cel mult 10^9. Afișăm suma maximă a exact k elemente consecutive, apoi poziția de început de la 1. La egalitate alegem prima secvență. Nu putem alege mai puțin de k elemente, chiar dacă toate numerele sunt negative.

Pentru 2 -1 4 3 -2 și k=3, sumele sunt 5, 6 și 5. Răspunsul este 6 2, corespunzător secvenței -1 4 3. Din suma 5 scădem 2 și adăugăm 3 pentru a obține 6.

Ferestrele de lungime 3 din 2,-1,4,3,-2 au sumele 5,6,5. A doua este maximă.Mărește schema ↗

Invariantul ferestrei

Calculăm separat suma primelor k valori. Apoi, la fiecare indice dr, suma nouă descrie exact intervalul de la dr-k+1 la dr. Valoarea eliminată este a[dr-k], cea care aparținea ferestrei precedente. Acest pas păstrează lungimea k fără să mai parcurgă interiorul intervalului.

Varianta cu tablou clasic

#include <iostream>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    long long a[1000];
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long suma = 0;
    for (int i = 0; i < k; ++i) suma += a[i];
    long long best = suma; int start = 0;
    for (int dr = k; dr < n; ++dr) {
        suma += a[dr] - a[dr-k];
        if (suma > best) { best = suma; start = dr-k+1; }
    }
    cout << best << ' ' << start+1 << '\n';
}

Varianta echivalentă cu std::vector

Indicii și datele de intrare rămân aceleași. Containerul este construit cu numărul de elemente folosite; accesul prin [] cere în continuare indici valizi.

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long suma = 0;
    for (int i = 0; i < k; ++i) suma += a[i];
    long long best = suma; int start = 0;
    for (int dr = k; dr < n; ++dr) {
        suma += a[dr] - a[dr-k];
        if (suma > best) { best = suma; start = dr-k+1; }
    }
    cout << best << ' ' << start+1 << '\n';
}

De ce inițializăm din prima sumă

Dacă am porni cu best=0, intrarea -5 -2 -3, k=2, ar produce o sumă care nu există. Cele două sume valide sunt -7 și -5, deci răspunsul corect este -5 2. Inițializarea dintr-o soluție reală respectă și cazurile negative.

Tabloul clasic are capacitatea 1000, dar algoritmul folosește numai n elemente. Suma poate ajunge în modul la 10^12, de aceea atât elementele, cât și suma sunt long long. Indicii rămân de tip int. Formula începutului conține +1 în indicii interni și încă +1 la afișarea poziției umane: cele două corecții au motive diferite.

Timpul total este O(n), memoria datelor O(n), iar starea auxiliară O(1). Soluția prin sume prefix are același ordin de timp pentru această cerință, dar păstrează informație utilă mai ales când urmează multe interogări independente.

Exersează

Pentru k=1, problema devine alegerea maximului și a primei sale poziții. Pentru k=n, există o singură fereastră. Pentru 1 1 1, k=2, rezultatul este 2 1, deoarece păstrăm prima dintre soluțiile egale.

Extinde programul pentru suma minimă, schimbând comparația, dar păstrând inițializarea din prima fereastră. Nu confunda această problemă cu secvența de lungime liberă sau cu o fereastră a cărei lungime variază după o condiție asupra sumei.

Continuă cu sume prefix, Kadane pentru lungime liberă și analiza timpului de execuție.

Întrebări frecvente

Ce este sliding window pentru o sumă de k elemente?

Este o fereastră de exact k poziții consecutive. După prima sumă, trecerea la fereastra următoare scade elementul ieșit și adaugă elementul intrat, astfel încât toate sumele se obțin în O(n).

Funcționează fereastra de lungime fixă și cu numere negative?

Da. Actualizarea sumei prin eliminarea și adăugarea unui element este validă și pentru valori negative. Inițializează maximul cu suma primei ferestre, nu cu zero.

Pot alege o secvență mai scurtă dacă toate valorile sunt negative?

Nu când cerința solicită exact k elemente. Rezultatul poate fi negativ. Alegerea unei secvențe vide sau mai scurte ar rezolva o altă problemă.