...
Eroare Algoritmi și structuri de date · Tablouri, două pointere și ferestre

Kadane returnează 0 pentru o listă doar cu numere negative

Pe scurt

Ai pornit maximul (sau suma curentă) de la 0, iar când toate numerele sunt negative, nicio secvență nu trece de 0. Pornește de la primul element: cel_mai_bun = curent = nums[0], apoi curent = max(x, curent + x) pentru restul.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Algoritmul lui Kadane găsește suma maximă a unei secvențe consecutive nevide. Varianta des întâlnită în tutoriale e: „resetează suma la 0 când devine negativă”. Merge când există măcar un număr pozitiv, dar pentru [-3, -1, -4] răspunsul corect e -1 (secvența formată doar din -1), iar codul returnează 0, adică suma unei secvențe goale, care nu e permisă.

Nu primești nicio eroare de la Python, doar un rezultat greșit pe un caz limită pe care testele îl verifică aproape întotdeauna. În „Repară tu” testul cu assert afișează rezultatul real.

Varianta sigură nu folosește 0 deloc: suma curentă e „cea mai bună secvență care se termină aici”, adică max(x, curent + x), iar maximul pornește de la primul element.

De ce apare: cauzele frecvente

1Maximul pornește de la 0

Greșit
PYTHON
cel_mai_bun, curent = 0, 0
for x in nums:
    curent = max(0, curent + x)
    cel_mai_bun = max(cel_mai_bun, curent)
Corect
PYTHON
cel_mai_bun = curent = nums[0]
for x in nums[1:]:
    curent = max(x, curent + x)
    cel_mai_bun = max(cel_mai_bun, curent)

Cu 0 ca punct de plecare, orice listă negativă dă 0. Pornind de la nums[0], maximul e mereu suma unei secvențe reale.

2Maximul pornește de la float('-inf'), dar curentul tot de la 0

Greșit
PYTHON
cel_mai_bun, curent = float('-inf'), 0
for x in nums:
    curent = max(0, curent + x)
    cel_mai_bun = max(cel_mai_bun, curent)
Corect
PYTHON
cel_mai_bun, curent = float('-inf'), 0
for x in nums:
    curent = max(x, curent + x)
    cel_mai_bun = max(cel_mai_bun, curent)

Problema nu e doar inițializarea: max(0, ...) înseamnă tot o secvență goală. max(x, curent + x) alege între a începe din nou de la x și a continua.

Repară tu

Repară eroarea, direct în pagină

Funcția profit_maxim(zile) calculează cel mai mare profit al unei perioade de zile consecutive (cel puțin o zi). Testul cu assert pică pentru lunile doar cu pierderi. Repar-o ca testele să treacă și să afișeze 6, -1 și -7.

Codul care dă eroarea
PYTHON
def profit_maxim(zile):
    cel_mai_bun = curent = 0
    for x in zile:
        curent = max(0, curent + x)
        cel_mai_bun = max(cel_mai_bun, curent)
    return cel_mai_bun

for zile, corect in [([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6), ([-3, -1, -4], -1), ([-7], -7)]:
    rez = profit_maxim(zile)
    assert rez == corect, f'profit gresit: {rez} in loc de {corect}'
    print(rez)
După reparație, programul afișează
6
-1
-7
Indiciu

Nu porni de la 0: maximul și suma curentă încep de la prima zi, iar suma curentă devine max(x, curent + x).

Cum o eviți pe viitor

La orice problemă de maxim sau minim, întreabă-te: „ce răspuns corect are o listă doar cu negative?” și „are voie secvența să fie goală?”. Inițializează maximul cu o valoare reală din date (primul element), nu cu 0. Testează mereu cu [-5], [-3, -1, -4] și o listă mixtă. Pentru lista goală decide explicit ce returnezi.

Întrebări frecvente

De ce varianta cu resetare la 0 apare în atâtea tutoriale?

Pentru că în unele formulări secvența goală e permisă (suma 0). Citește enunțul: dacă cere o secvență nevidă, 0 e greșit pentru liste negative.

Care e complexitatea?

O(n) timp și O(1) memorie, în ambele variante. Reparația nu schimbă viteza.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.