h1(#cuburi5). 'Cuburi5':problema/cuburi5

h1(#cuburi5). 'Cuburi5':problema/cuburi5
 
O soluţie evidentă în O(N^2^ * K) (sau O(N^2^ * K^2^)) este asemănătoare găsirii 'subşirului crescător maximal':problema/scmax. Putem îmbunătăţi această soluţie folosindu-ne de faptul că numerele înscrise pe cuburi sunt din intervalul [1..10^5^]. Vom parcurge cuburile începând cu _ultimul_ (pentru a putea găsi prima soluţie lexicografică uşor) şi ne vom menţine un vector _best_ de mărime 10^5^ având semnificaţia: _best[i]_ = lungimea maximă a unui subşir care începe cu un cub pe care este înscris numărul i. Pentru a găsi lungimea maximă a unui subşir care începe cu un cub dat, ne vom uita la toate valorile _best[i]_ pentru care valoarea i este înscrisă pe cub. După ce calculăm această valoare pentru un cub, va trebui sa reactualizăm vectorul _best_. Aceasă soluţie are complexitatea O(N * K) şi obţine 100 de puncte.