Secvența de sumă maximă: algoritmul Kadane

Algoritmul Kadane găsește suma maximă a unei secvențe nevide de elemente consecutive în timp liniar. Valorile pot fi pozitive, zero sau negative. Cerința de consecutivitate diferențiază problema de alegerea oricăror elemente convenabile.

Vom calcula suma, apoi vom explica ce informație suplimentară permite reconstruirea capetelor. Presupunem explicit că secvența vidă nu este permisă, astfel încât un șir numai cu valori negative trebuie să dea un rezultat negativ.

Cum funcționează

Notăm ending suma maximă a unei secvențe care se termină exact la poziția curentă. Pentru următorul element x, avem două posibilități: începem o secvență nouă numai cu x sau prelungim cea mai bună secvență anterioară. Prin urmare, noua valoare este max(x,ending+x). Variabila best păstrează cel mai bun rezultat dintre toate capetele deja analizate.

Inițializăm ambele variabile cu primul element. Pornirea de la zero ar introduce implicit posibilitatea unei secvențe vide și ar da un răspuns greșit pentru date numai negative. Fiecare pas folosește valoarea veche a lui ending numai pentru poziția precedentă, deci nu avem nevoie de un tablou de stări dinamice.

Programul acceptă 1 <= n <= 100000 și elemente cu modulul cel mult un miliard. Tabloul clasic are capacitatea 100000 și indicii logici 0..n-1. Vectorul echivalent are n elemente. Folosim long long pentru sume. Tabloul este păstrat pentru a face relația cu pozițiile explicită, însă dacă dorim doar suma, putem citi valorile pe rând și păstra numai cele două variabile.

Exemplu urmărit pas cu pas

Pentru valorile -2, 3, -1, 4, -5, sumele ending sunt -2, 3, 2, 6, 1. La elementul 3 preferăm o secvență nouă, deoarece 3 este mai mare decât -2+3. La -1 continuăm, fiindcă suma 2 este mai bună decât -1.

Cel mai bun rezultat este 6, obținut din 3,-1,4. Observă că o valoare negativă poate face parte din secvența optimă: ea poate uni două porțiuni suficient de bune. Pentru -7,-2,-9, răspunsul este -2, secvența formată din elementul cel mai mare.

Implementare C++17

Varianta cu tablou clasic:

#include <algorithm>
#include <iostream>
int main() {
    int n;
    std::cin >> n;
    long long a[100000];
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    long long ending = a[0], best = a[0];
    for (int i = 1; i < n; ++i) {
        ending = std::max(a[i], ending + a[i]);
        best = std::max(best, ending);
    }
    std::cout << best << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <algorithm>
#include <iostream>
#include <vector>
int main() {
    int n;
    std::cin >> n;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    long long ending = a[0], best = a[0];
    for (int i = 1; i < n; ++i) {
        ending = std::max(a[i], ending + a[i]);
        best = std::max(best, ending);
    }
    std::cout << best << '\n';
}

De ce funcționează și cât costă

Orice secvență care se termină la i are fie un singur element, fie rezultă prin adăugarea lui a[i] la o secvență terminată la i-1. Alegerea maximului acoperă toate posibilitățile. Maximul acestor stări este maximul global.

Timpul este O(n). Implementarea cu date memorate ocupă O(n), iar starea algoritmului O(1). Pentru reconstruire, reținem începutul curent și actualizăm capetele răspunsului când best se îmbunătățește, precizând regula de departajare.

Greșeli frecvente

Nu selecta doar valorile pozitive: astfel pierzi consecutivitatea. Nu confunda secvența cu subșirul. Nu reseta rezultatul final la zero când enunțul interzice secvența vidă. Verifică separat n=1.

Exersează

Care este rezultatul pentru 4,-6,5,2 și unde începe secvența optimă?

Rezolvare explicată: Stările ending sunt 4,-2,5,7. Răspunsul este 7 pentru ultimele două elemente; după suma negativă, începerea la 5 este mai bună decât prelungirea.

Continuă să înveți

Secvențe, programare dinamică și maxime.

Întrebări frecvente

Kadane funcționează când toate numerele sunt negative?

Da, dacă stările sunt inițializate cu primul element. Rezultatul va fi cea mai mare valoare, luată ca secvență de lungime unu.

De ce nu eliminăm fiecare număr negativ?

Elementele trebuie să rămână consecutive. O valoare negativă interioară poate fi necesară pentru a lega două porțiuni a căror sumă totală este mai bună.

Care este diferența dintre secvență și subșir?

Secvența folosește poziții consecutive. Un subșir păstrează ordinea, dar poate sări poziții. Algoritmii și răspunsurile pot fi complet diferite.

Pot afla și capetele secvenței?

Da. Păstrează începutul candidatului curent și copiază-l împreună cu poziția finală când actualizezi maximul global. Pentru egalități stabilește o regulă explicită.

Este necesar să memorez tot vectorul?

Nu pentru calculul sumei. Poți prelucra intrarea pe rând, folosind memorie auxiliară constantă. Memorarea poate fi utilă pentru afișarea ulterioară a elementelor.