Secvențe și subsecvențe

O secvență a unui șir conține elemente de pe poziții consecutive. În [2,4,6], [2,4] este secvență, iar [2,6] nu este. Un subșir păstrează ordinea din șirul inițial, dar poate sări peste poziții; [2,6] este subșir. Pentru a calcula repede suma unei secvențe, folosim sumele parțiale. Dacă valorile sunt 2, 4, 6, sumele parțiale sunt 2, 6, 12, iar suma ultimelor două valori este 12−2=10.

O secvență (subsecvență) a unui vector este formată din elemente aflate pe poziții consecutive, de la $l$ la $r$, cu ambele capete incluse; are $r-l+1$ elemente. Un subșir păstrează ordinea elementelor din șirul inițial, dar poate sări peste poziții. Pentru $[2,4,6]$, $[2,4]$ este secvență și subșir, iar $[2,6]$ este subșir, dar nu secvență. Pozițiile se numerotează de la 0 sau de la 1, iar convenția se precizează: în exemplele de mai jos indicii pornesc de la 0, dacă nu se spune altfel.

Suma unei secvențe se calculează printr-un ciclu de la $l$ la $r$, cu cost proporțional cu lungimea secvenței. Dacă se cer multe sume pe același vector, se construiește o dată vectorul sumelor parțiale (al prefixelor): $s_0=0$ și $s_i=a_1+\cdots +a_i$ pentru indici de la 1. Suma secvenței cu pozițiile de la $l$ la $r$ (indici de la 1) este $s_r-s_{l-1}$, adică o scădere, în timp constant.

Exemplul 1 — suma unei secvențe. În vectorul $3,1,4,2$ (indici de la 0) secvența cu $l=1$ și $r=2$ conține elementele 1 și 4, cu suma 5.

#include <iostream>
using namespace std;
int main() {
    int v[] = {3, 1, 4, 2};
    int l = 1, r = 2, suma = 0;
    for (int i = l; i <= r; ++i)
        suma += v[i];
    cout << suma;
    return 0;
}

Se afișează 5. Secvența are $r-l+1=2$ elemente. Dacă ciclul ar avea condiția i < r, elementul de pe poziția $r$ ar lipsi și suma ar fi 1.

Exemplul 2 — sume parțiale. Pentru $[3,1,4,2]$, cu indici de la 1, sumele parțiale sunt $s=(0;3;4;8;10)$. Suma pozițiilor 2–3 (elementele 1 și 4) este $s_3-s_1=8-3=5$, iar suma întregului vector este $s_4=10$. Fiecare întrebare nouă despre suma unei secvențe costă acum o singură scădere.

int pre[5] = {0};
for (int i = 0; i < 4; ++i)
    pre[i + 1] = pre[i] + v[i];
cout << pre[3] - pre[1] << ' ' << pre[4];

Secvența afișează 5 10. Vectorul pre are cu un element mai mult decât v, iar pre[0] este 0, ca să funcționeze și secvențele care încep de la primul element.

Exemplul 3 — cea mai lungă secvență de elemente egale. În vectorul $1,1,2,2,2,3,2,2$ se numără lungimea secvenței curente: crește când elementul este egal cu cel dinaintea lui și revine la 1 altfel. Lungimile succesive sunt 1, 2, 1, 2, 3, 1, 1, 2, iar maximul lor este 3, pentru secvența $2,2,2$. Valoarea 2 apare de 5 ori în vector, dar secvența lor maximă are lungimea 3, pentru că elementul 3 le întrerupe.

int best = 1, cur = 1;
for (int i = 1; i < n; ++i) {
    if (y[i] == y[i - 1]) ++cur; else cur = 1;
    if (cur > best) best = cur;
}

Secvența lasă best = 3. Algoritmul parcurge vectorul o singură dată, deci timpul este proporțional cu $n$.

Exemplul 4 — câte secvențe și câte subșiruri are un vector. Un vector cu $n$ elemente are $n$ secvențe de lungime 1, $n-1$ de lungime 2 și așa mai departe, până la una de lungime $n$, deci $\frac{n(n+1)}{2}$ secvențe. Pentru $[3,1,4,2]$ sunt $4+3+2+1=10$. Subșirurile nevide corespund submulțimilor nevide de poziții, deci sunt $2^n-1=15$. Diferența, 5, reprezintă subșirurile care sar peste cel puțin o poziție: $[3,4]$, $[3,2]$, $[1,2]$, $[3,1,2]$ și $[3,4,2]$. Numărul secvențelor crește pătratic, iar cel al subșirurilor exponențial; de aceea un program care ar încerca toate subșirurile unui vector de 40 de elemente nu mai este practic.

Greșeli frecvente

• Greșit: $[2,6]$ este o secvență a lui $[2,4,6]$.
  Corect: este subșir; o secvență are poziții consecutive.
• Greșit: secvența de la $l$ la $r$ are $r-l$ elemente.
  Corect: are $r-l+1$ elemente când ambele capete sunt incluse.
• Greșit: sumele parțiale se recalculează pentru fiecare întrebare.
  Corect: se construiesc o dată, apoi fiecare suma se obține prin diferența a două prefixe.

Înainte și după