...
Eroare Algoritmi și structuri de date · Programare dinamică și memoizare

Cel mai lung subșir crescător returnează dp[-1] în loc de max(dp)

Pe scurt

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ă

Greșit
PYTHON
return dp[-1]
Corect
PYTHON
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

Greșit
PYTHON
curent = [nums[0]]
for x in nums[1:]:
    curent.append(max(x, curent[-1] + x))
return curent[-1]
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
3
1
4
Indiciu

Răspunsul e cel mai mare dp[i], nu dp[-1].

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

← 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.