Secvența de sumă maximă

De ce contează?

Urmărești profitul zilnic al unui magazin — unele zile pe plus, altele pe minus. Vrei intervalul de zile consecutive cu profitul total cel mai mare. Dacă suma de până acum a intrat pe minus, te trage în jos: mai bine reîncepi de la ziua curentă. Asta face Kadane.

Problema: cea mai bună subsecvență contiguă

Vrei subsecvența contiguă cu suma maximă. Pe valori pozitive, răspunsul e tot vectorul. Interesant devine când apar valori negative: uneori merită să le incluzi (dacă „leagă" două zone bune), alteori nu.

Ideea lui Kadane: arunci povara

Parcurgi o singură dată. Ții sumaCurenta = cea mai bună sumă care se termină la poziția curentă. La fiecare element decizi:

sumaCurenta = max(element, sumaCurenta + element)

Dacă sumaCurenta de până acum a devenit negativă, te trage în jos — o arunci și reîncepi de la elementul curent.

Algoritm pas cu pas:

element	sumaCurenta = max(el, sumaCurenta+el)	maxSuma
−2	−2	−2
3	max(3, −2+3=1) = 3	3
−1	max(−1, 3−1=2) = 2	3
4	max(4, 2+4=6) = 6	6
−5	max(−5, 6−5=1) = 1	6
2	max(2, 1+2=3) = 3	6

Răspuns: 6 (secvența 3, −1, 4).

v	-2	3	-1	4	-5	2
i	0	1	2	3	4	5

Secvența de sumă maximă este v[1..3] = 3, −1, 4, cu suma 6. Deși −1 e negativ, merită inclus fiindcă leagă 3 de 4.

Implementare C++

#include <iostream>
#include <algorithm>
using namespace std;

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

    long long sumaCurenta = v[0];
    long long maxSuma = v[0];        // initializam cu primul element
    for (int i = 1; i < n; i++) {
        sumaCurenta = max((long long)v[i], sumaCurenta + v[i]);
        maxSuma = max(maxSuma, sumaCurenta);
    }
    cout << maxSuma << "\n";         // 6
    return 0;
}

Observația-cheie

max(v[i], sumaCurenta + v[i]) e inima algoritmului: dacă suma de până acum plus elementul e mai mică decât elementul singur, înseamnă că trecutul te încurca — reîncepi de la v[i]. O singură trecere, O(n).

De ce inițializăm cu primul element

Pe un vector cu toate valorile negative (ex. {-3, -1, -2}), răspunsul corect e cel mai mare element (-1), nu 0. Dacă pornești maxSuma de la 0, raportezi greșit 0 — o sumă pe care nicio secvență nu o atinge. Pornește de la v[0].

Complexitate

Metodă	Timp	Spațiu
Kadane	O(n)	O(1)
toate subsecvențele	O(n²) sau O(n³)	O(1)

Greșeli frecvente

Capcane reale la Kadane:

maxSuma inițializat cu 0: greșit pe vectori cu toate valorile negative. Pornește de la v[0].
Confuzi sumaCurenta cu maxSuma: sumaCurenta se poate „reseta", dar maxSuma doar crește (reține cel mai bun rezultat văzut).
Overflow: sume lungi de valori mari se sparg; folosește long long.
Aplici pe „subșir" în loc de „subsecvență": Kadane e pentru secvențe contigue; pentru subșiruri (cu sărituri) e altă problemă.

Vizualizare

Urmărește cum suma curentă crește, se resetează când devine o povară, iar maximul reține cel mai bun rezultat:

Indiciu

Observă momentele de „reset": când suma curentă ar deveni mai mică decât elementul singur, secvența reîncepe. Maximul global nu scade niciodată.

De reținut

Kadane găsește subsecvența contiguă de sumă maximă, în O(n).
Decizia: sumaCurenta = max(element, sumaCurenta + element); arunci trecutul când devine povară.
Inițializează maxSuma cu v[0] (nu 0) și folosește long long.