Complexitatea optima este {$O(N*log{~2~}N)$}. La fiecare pas $i$ trebuie determinata lungimea cea mai mare $best{~j~}$ unde {$1 &le; j < i$} astfel incat {$a{~j~}$} &le; {$a{~i~}$}. Pentru a afla aceasta informatie in timp optim {$O(log{~2~}N)$} se poate folosi un arbore de intervale sau un arbore indexat binar. O astfel de abordare obtine 100 de puncte si se gaseste 'aici':job_detail/146356?action=view-source. O alta idee de rezolvare ce obtine punctajul maxim, dar mai simplu de implementat si mai rapida, se gaseste 'aici':job_detail/146355?action=view-source. Ideea de rezolvare din spatele acestei solutii se gaseste in cartea lui Catalin Francu, "Psihologia concursurilor de informatica", editura L&S.
Printre problemele care folosesc ideile de mai sus se numara:

'euro2':problema/euro2
'interclasare':problema/interclasare
'cuburi3':problema/cuburi3
'subsiruri':problema/subsiruri
'subsir2':problema/subsir2

 
* 'Euro 2':problema/euro2
* 'Interclasare':problema/interclasare
* 'Cuburi3':problema/cuburi3
* 'Subsiruri':problema/subsiruri
* 'Subsir2':problema/subsir2

== include(page="template/taskfooter" task_id="scmax") ==