Cuburi5

O soluţie evidentă în O(N² * K) (sau O(N² * K²)) este asemănătoare găsirii subşirului crescător maximal. Putem îmbunătăţi această soluţie folosindu-ne de faptul că numerele înscrise pe cuburi sunt din intervalul [1..10⁵]. 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⁵ 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.