Secvențe și sume prefix în C++

O secvență este o porțiune de elemente consecutive dintr-un vector. În 2 3 -1 4 5 6 0, valorile 4 5 6 formează o secvență, dar 2 4 6 nu sunt consecutive. Pentru a descrie o secvență poți folosi indicele de început și indicele de sfârșit.

Recapitulează parcurgerea vectorilor și sumele și numărările. Vom rezolva două cerințe diferite: cea mai lungă porțiune de valori pozitive și suma unei porțiuni indicate prin capete.

Cea mai lungă secvență de numere pozitive

Citim n, cu 0 <= n <= 100000, și n întregi între -1000000 și 1000000. Calculăm lungimea maximă a unei secvențe în care toate elementele sunt strict pozitive. Dacă nu există niciun număr pozitiv, răspunsul este zero.

Varianta cu tablou clasic

Tabloul a[100000] are capacitate fixă. Datele ocupă doar primele n poziții, iar indicii folosiți sunt de la 0 la n - 1. Limita lui n trebuie să respecte această capacitate.

#include <iostream>

int main() {
    int n = 0;
    std::cin >> n;
    int a[100000]{};
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    int curenta = 0, maxima = 0;
    for (int i = 0; i < n; ++i) {
        int x = a[i];
        if (x > 0) {
            ++curenta;
        } else {
            curenta = 0;
        }
        if (curenta > maxima) {
            maxima = curenta;
        }
    }
    std::cout << maxima << '\n';
    return 0;
}

Varianta cu std::vector

std::vector<int> a(n) creează exact n elemente. Citirea, accesul a[i] și algoritmul rămân aceleași; se schimbă declararea și modul de gestionare a dimensiunii.

#include <iostream>
#include <vector>

int main() {
    int n = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    int curenta = 0, maxima = 0;
    for (int i = 0; i < n; ++i) {
        int x = a[i];
        if (x > 0) {
            ++curenta;
        } else {
            curenta = 0;
        }
        if (curenta > maxima) {
            maxima = curenta;
        }
    }
    std::cout << maxima << '\n';
    return 0;
}

Pentru 2 3 -1 4 5 6 0, lungimea curentă evoluează 1, 2, 0, 1, 2, 3, 0, iar maximul final este 3. Valoarea negativă și zero întrerup secvența. Variabila maxima păstrează însă cel mai bun rezultat anterior, deci nu se resetează odată cu curenta.

În cele două variante am memorat datele pentru a compara reprezentările. Putem însă prelucra fiecare număr imediat după citire, fără să memorăm întregul vector: el influențează doar cei doi contori. După prelucrarea unui element, curenta este lungimea secvenței pozitive care se termină chiar acolo. Actualizarea maximului la fiecare pas tratează corect și cazul în care cea mai lungă secvență ajunge la ultimul element.

Sume prefix: calculezi o dată, refolosești

Când ai multe întrebări de forma „care este suma de la indicele stanga la indicele dreapta, inclusiv?”, o parcurgere completă pentru fiecare întrebare poate fi costisitoare. Construim un vector prefix cu un element în plus.

Definim prefix[0] = 0, iar prefix[k] este suma primelor k elemente. Pentru a = 2 -1 3 4, obținem prefix = 0 2 1 4 8. Observă că numărul din indicele lui prefix spune câte elemente au fost adunate.

Prefixul are n + 1 elemente. Suma pe intervalul inclusiv [1, 3] este 6.

Pentru intervalul inclusiv [stanga, dreapta], scădem prefix[stanga] din prefix[dreapta + 1]. Primul termen conține toate elementele până la capătul drept, iar al doilea elimină exact elementele aflate înaintea capătului stâng.

Mai multe întrebări despre același vector

Programul citește n și q, apoi n valori și q perechi de indici. Cerem 1 <= n <= 100000, 0 <= q <= 100000, valori între -1000000 și 1000000 și 0 <= stanga <= dreapta < n pentru fiecare întrebare.

Varianta cu tablou clasic

Tabloul prefix[100001] permite n <= 100000 și păstrează și poziția 0 pentru prefixul gol. Acoladele inițializează toate valorile cu zero.

#include <iostream>

int main() {
    int n = 0, q = 0;
    std::cin >> n >> q;
    long long prefix[100001]{};
    for (int i = 0; i < n; ++i) {
        long long x = 0;
        std::cin >> x;
        prefix[i + 1] = prefix[i] + x;
    }
    for (int i = 0; i < q; ++i) {
        int stanga = 0, dreapta = 0;
        std::cin >> stanga >> dreapta;
        std::cout << prefix[dreapta + 1] - prefix[stanga] << '\n';
    }
    return 0;
}

Varianta cu std::vector

std::vector<long long> prefix(n + 1, 0) creează exact n + 1 elemente, inițializate cu zero. Formula și indicii folosiți în calcule sunt identici cu cei din varianta clasică.

#include <iostream>
#include <vector>

int main() {
    int n = 0, q = 0;
    std::cin >> n >> q;
    std::vector<long long> prefix(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        long long x = 0;
        std::cin >> x;
        prefix[i + 1] = prefix[i] + x;
    }
    for (int i = 0; i < q; ++i) {
        int stanga = 0, dreapta = 0;
        std::cin >> stanga >> dreapta;
        std::cout << prefix[dreapta + 1] - prefix[stanga] << '\n';
    }
    return 0;
}

Pentru vectorul anterior, întrebările 1 3, 0 3 și 2 2 produc 6, 8 și 3, pe linii separate. Formula funcționează și cu valori negative, cu un singur element sau cu un interval care începe la zero.

Limite și cost

Algoritmul secvenței pozitive are timp O(n) și folosește doi contori, adică O(1) spațiu suplimentar față de datele memorate. Varianta care prelucrează direct la citire ar avea memorie totală suplimentară O(1). Algoritmul cu prefixe le construiește în O(n) și răspunde fiecărei întrebări în O(1). Pentru toate întrebările, timpul este O(n + q).

Nu confunda suma prefix cu elementul original. De asemenea, formula presupune că valorile nu se modifică între întrebări. Dacă schimbi un element, prefixele calculate anterior pot deveni incorecte și trebuie actualizate printr-o metodă potrivită.

În variantele clasice, memoria rezervată este dată de capacitatea din declarație, nu de numărul de elemente folosite. În variantele cu std::vector, stocarea din aceste exemple este proporțională cu dimensiunile citite. Algoritmul și numărul de elemente prelucrate nu se schimbă între reprezentări. Inițializarea cu {} a tabloului clasic pune la zero întreaga capacitate, inclusiv pozițiile nefolosite; acest cost este separat de parcurgerea celor n elemente sau a celor n * m celule.

Exersează

1. Care este secvența pozitivă maximă în 0 -2 0?
2. Ce lungime obții pentru -1 2 3 4?
3. Ce sumă are intervalul [0, 0] în exemplul cu prefixe?
4. De ce vectorul de prefixe are n + 1 poziții?

Răspunsuri: lungime 0; lungime 3, inclusiv elementul final; suma este 2; păstrăm separat prefixul gol, apoi sumele primelor 1, 2, ..., n elemente. Această convenție elimină un caz special pentru intervalele care încep la zero.

Continuă cu tablourile bidimensionale.