h3. Rezolvare:
O să începem prin a da altă îmbrăcăminte problemei. Astfel, să ne imaginăm că am construi un arbore binar de căutare pe şirul dat, având drept chei poziţiile din şir, şi drept valori auxiliare valorile poziţiilor respective din şir (un nod cu cheia $i$ va avea valoarea auxiliara $a{~i~}$.

Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul, pe care îl considerăm de acum ca fixat. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este proastă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.
 
Acum, să observăm că dacă considerăm costul unui drum în arbore de la rădăcină la o frunză să fie suma valorilor auxiliare din drumul (unic) respectiv, atunci se observă că costul strategiei bazate pe acest arbore este chiar costul maxim al unui drum ! Să exemplificăm pe şirul din exemplu:
 
Se observă că cel mai lung
 

Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este proastă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.
Acum, să observăm că dacă considerăm costul unui drum în arbore să fie suma

h2. Programare dinamica folosind bitmask