Cel mai lung subșir crescător
O aplicație de fitness îți arată greutățile ridicate la sală, antrenament după antrenament. Care este cea mai lungă serie de antrenamente (nu neapărat consecutive) în care ai crescut mereu greutatea? Aceasta este problema celui mai lung subșir crescător, cu o soluție DP în O(n²) și una foarte elegantă în O(n log n).
Problema
Un subșir se obține ștergând câteva elemente din listă, fără să schimbi ordinea celor rămase. Cauți lungimea celui mai lung subșir strict crescător.
Scrie două funcții pentru cel mai lung subșir strict crescător: lis_patratic(lista) cu tabelul dp (O(n²)) și lis_rapid(lista) cu lista de cozi și bisect_left (O(n log n)). Testele afișează rezultatele ambelor metode pe aceeași linie.
- În lis_patratic: dp = [1] * n, două bucle, răspunsul max(dp).
- În lis_rapid: pentru fiecare x, p = bisect_left(cozi, x), apoi append sau înlocuire.
- Trebuie să apară: 4 4, 4 4, 1 1, 0 0.
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan