Secvențe de valori

De ce contează?

Privești strada printr-o fereastră de tren în mișcare: la fiecare moment vezi un segment, iar când trenul avansează, un copac nou intră în cadru și unul vechi iese. Așa funcționează fereastra glisantă peste un vector — un interval care alunecă, actualizat incremental.

Secvențe contigue și fereastra glisantă

O secvență (subsecvență contiguă) e un bloc de poziții consecutive, ex. v[2..5]. Multe probleme cer ceva despre toate secvențele de o anumită lungime: suma, maximul, media. Tehnica ferestrei glisante le rezolvă fără să recalculezi totul de fiecare dată.

Ideea: actualizare incrementală

La suma fiecărei secvențe de lungime k: în loc să resumezi k elemente la fiecare poziție (O(n·k)), aluneci fereastra — adaugi elementul care intră la dreapta și scazi pe cel care iese la stânga:

suma_nouă = suma_veche + v[intrat] − v[ieșit]

v	5	3	8	1	9	2
i	0	1	2	3	4	5

Fereastră de lungime 3 pe pozițiile [1,3]: suma = 3+8+1 = 12. La pasul următor iese v[1]=3, intră v[4]=9 → suma = 12 − 3 + 9 = 18.

Algoritm pas cu pas: sume de secvențe de lungime 3

v = {5, 3, 8, 1, 9, 2}:

fereastră	elemente	sumă	cum
[0,2]	5 3 8	16	(prima, calculată direct)
[1,3]	3 8 1	12	16 − 5 + 1
[2,4]	8 1 9	18	12 − 3 + 9
[3,5]	1 9 2	12	18 − 8 + 2

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int v[1000];
    for (int i = 0; i < n; i++) cin >> v[i];

    long long suma = 0;
    for (int i = 0; i < k; i++) suma += v[i];   // prima fereastra
    long long maxSuma = suma;

    for (int i = k; i < n; i++) {
        suma += v[i] - v[i - k];    // intra v[i], iese v[i-k]
        if (suma > maxSuma) maxSuma = suma;
    }
    cout << maxSuma << "\n";        // suma maxima a unei secvente de lungime k
    return 0;
}

Observația-cheie

Cheia e v[i] - v[i - k]: v[i] intră în fereastră, v[i - k] (cel de acum k poziții) iese. O singură adunare și o scădere per pas — de aici O(n) în loc de O(n·k).

Fereastră de lungime variabilă

Unele probleme cer „cea mai lungă secvență cu suma ≤ X". Acolo fereastra își schimbă lungimea: extinzi dreapta cât timp condiția ține, altfel micșorezi stânga. Aceeași idee de intrare/ieșire, dar capetele se mișcă independent.

Complexitate

Metodă	Timp	Spațiu
fereastră glisantă	O(n)	O(1)
recalculare naivă	O(n·k)	O(1)

Greșeli frecvente

Capcane reale la fereastra glisantă:

Recalculezi toată fereastra: resumezi k elemente la fiecare pas → O(n·k), prea lent. Adaugă intratul, scade ieșitul.
Indice greșit la ieșire: elementul care iese e v[i - k], nu v[i - k + 1]. Greșeala de o poziție corupe toate sumele.
Prima fereastră necalculată: uiți să însumezi primele k elemente înainte de buclă → pornești de la 0.
Overflow: sumele de secvențe lungi se pot sparge; long long.

Vizualizare

Urmărește cum fereastra alunecă și cum suma se actualizează adăugând și scăzând câte un element:

Indiciu

Observă că la fiecare pas se schimbă doar două elemente: unul intră, unul iese. Restul ferestrei rămâne neatins — de aceea nu trebuie resumat.

De reținut

Fereastra glisantă = interval contiguu care alunecă; actualizezi incremental (intră/iese).
suma += v[i] - v[i-k] → O(n) în loc de O(n·k); calculează prima fereastră separat.
Lungime fixă sau variabilă; atenție la indicele celui care iese și la overflow.