Cel mai lung subșir crescător returnează dp[-1] în loc de max(dp)
dp[i] e lungimea celui mai lung subșir crescător care se termină chiar la poziția i, nu cea mai bună din tot șirul. Răspunsul e maximul din tot tabelul: return max(dp, default=0), nu dp[-1].
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
În multe probleme DP, valoarea dp[i] are o definiție precisă: „cel mai bun rezultat care se termină la i”. La cel mai lung subșir crescător (LIS), dp[i] e lungimea celui mai lung subșir crescător care îl folosește pe nums[i] ca ultim element.
Cel mai lung subșir din tot șirul se poate termina oriunde, nu neapărat pe ultima poziție. Pentru [3, 10, 2, 11, 1], dp e [1, 2, 1, 3, 1]: răspunsul e 3 (3, 10, 11), dar dp[-1] e 1, pentru că ultimul element e cel mai mic.
Nu primești nicio eroare, iar pe multe exemple ultimul element e chiar maximul, deci testele simple trec. Aceeași capcană apare la suma maximă a unei secvențe (Kadane), la cel mai lung subșir comun cu terminare fixă și la orice definiție „care se termină la i”.
De ce apare: cauzele frecvente
1Rezultatul citit din ultima celulă
return dp[-1]return max(dp, default=0)max caută cel mai bun subșir indiferent unde se termină. default=0 tratează lista goală.
2Aceeași greșeală la Kadane
curent = [nums[0]]
for x in nums[1:]:
curent.append(max(x, curent[-1] + x))
return curent[-1]curent = [nums[0]]
for x in nums[1:]:
curent.append(max(x, curent[-1] + x))
return max(curent)curent[i] e cea mai bună secvență care se termină la i, deci răspunsul e maximul lor.
Repară eroarea, direct în pagină
Funcția lis(nums) calculează lungimea celui mai lung subșir strict crescător. Testul cu assert pică: funcția returnează ultima celulă a tabelului. Repar-o ca să afișeze 3, 1 și 4.
def lis(nums):
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return dp[-1]
for nums, corect in [([3, 10, 2, 11, 1], 3), ([5, 4, 3], 1), ([10, 9, 2, 5, 3, 7, 101, 18], 4)]:
rez = lis(nums)
assert rez == corect, f'lungime gresita: {rez} in loc de {corect}'
print(rez)3 1 4
Indiciu
Răspunsul e cel mai mare dp[i], nu dp[-1].
Reparația
def lis(nums):
dp = [1] * len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp, default=0)
for nums, corect in [([3, 10, 2, 11, 1], 3), ([5, 4, 3], 1), ([10, 9, 2, 5, 3, 7, 101, 18], 4)]:
rez = lis(nums)
assert rez == corect, f'lungime gresita: {rez} in loc de {corect}'
print(rez)De ce merge
dp[i] e lungimea celui mai lung subșir crescător care se termină la poziția i. Pentru [3, 10, 2, 11, 1], tabelul e [1, 2, 1, 3, 1]: ultimul element, 1, nu poate continua niciun subșir, deci dp[-1] e 1. Cel mai lung subșir (3, 10, 11) se termină la poziția 3, iar max(dp) îl găsește oriunde s-ar termina.
Cum o eviți pe viitor
Scrie definiția lui dp[i] într-un comentariu înainte de a scrie codul. Dacă definiția conține „se termină la i”, răspunsul final e un maxim (sau minim) peste tot tabelul; dacă e „folosind primele i elemente”, răspunsul e în ultima celulă. Testează cu un șir în care ultimul element e cel mai mic.
Întrebări frecvente
Există o variantă mai rapidă decât O(n²)?
Da, cu căutare binară: păstrezi pentru fiecare lungime cel mai mic final posibil și folosești bisect_left. Complexitatea devine O(n log n).
Când e corect dp[-1]?
Când dp[i] înseamnă „cel mai bun rezultat folosind primele i elemente”, ca la rucsac sau la numărul de moduri. Atunci tabelul e crescător după informație și ultima celulă conține răspunsul.
Erori înrudite
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. 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). IndexError: list index out of range la dp[n] (tabelul DP e prea scurt) Ai creat tabelul cu dp = [0] * n, dar răspunsul e dp[n], iar o listă cu n elemente are doar indicii 0..n-1. Când dp[i] înseamnă „primele i elemente” sau „treapta i”, tabelul are nevoie de n + 1 poziții: dp = [0] * (n + 1). Î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.
