Kadane returnează 0 pentru o listă doar cu numere negative
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
cel_mai_bun, curent = 0, 0
for x in nums:
curent = max(0, curent + x)
cel_mai_bun = max(cel_mai_bun, curent)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
cel_mai_bun, curent = float('-inf'), 0
for x in nums:
curent = max(0, curent + x)
cel_mai_bun = max(cel_mai_bun, curent)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ă 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.
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)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).
Reparația
def profit_maxim(zile):
cel_mai_bun = curent = zile[0]
for x in zile[1:]:
curent = max(x, 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)De ce merge
Cu 0 ca punct de plecare și max(0, ...), codul accepta tacit o perioadă de zero zile, cu profit 0, care e mai mare decât orice pierdere. Acum curent e cel mai bun profit al unei perioade care se termină în ziua curentă: fie continuăm perioada (curent + x), fie începem una nouă chiar azi (x). Maximul pornește de la prima zi, deci e mereu profitul unei perioade reale.
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
ValueError: max() iterable argument is empty Ai apelat max() (sau min()) pe o listă goală, deci nu există un maxim. Tratează lista goală înainte (if not lista: return ...) sau dă-i lui max o valoare implicită: max(lista, default=0). Fereastra glisantă sare peste ultima fereastră (off-by-one la range) O listă cu n elemente are n - k + 1 ferestre de lungime k, deci bucla trebuie să fie range(len(lista) - k + 1). Cu range(len(lista) - k) ultima fereastră nu e verificată, iar rezultatul e greșit fără nicio eroare. Suma pe interval cu sume prefix iese greșită (prefix[j] - prefix[i] fără +1) Cu prefix[k] = suma primelor k elemente, suma de la i la j inclusiv este prefix[j + 1] - prefix[i]. Dacă scrii prefix[j] - prefix[i], pierzi elementul j; dacă scrii prefix[j] - prefix[i - 1] cu altă convenție, pici la i = 0. Î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.
