h3. Soluţie:

Voi face un desen pentru explicaţii. :)

Şi această soluţie foloseşte metoda programării dinamice. Construim <tex> bst_{i} </tex> egal cu costul minim de a împărţi primele <tex> i </tex> numere din <tex> S </tex>. Pentru a calcula <tex> bst_{i} </tex> alegem toate secvenţele posibile care se termină pe o poziţia <tex> j </tex>, <tex> j < i </tex>, şi adunăm valorile corespunzătoare:
 
* <tex> bst_{i} = Min\{bst_{j} + Max\{S_{j+1},.., S_{i}\}\ :\ 0 \le j < i, \displaystyle\sum_{k=j+1}^{i} S_{k} \le M\}; </tex>
 
Implementarea directă a acestei recurenţe conduce la un algoritm de complexitate <tex> O(N^{2}) </tex>, dar care pentru restricţiile impuse nu este de ajuns.
 
Să obţinem în continuare alte informaţii. Fie indicele <tex> j </tex> minim astfel încât <tex> \displaystyle\sum_{k=j+1}^{i} \le M </tex>. Maximul obţinut din mulţimea <tex> \{S_{j+1},.., S_{i}\} </tex> se găseşte pe o poziţie <tex> j^{'} </tex> unde <tex> j < j^{'} \le i </tex>. Însă, orice indice <tex> k </tex> cu <tex> j \le k < j^{'} </tex> are proprietatea că rezultatul expresiei <tex> Max\{S_{k+1},.., S_{i}\} </tex> se găseşte pe poziţia <tex> j^{'} </tex>. Rezultă că <tex> \forall k \in \{j, j+1,.., j^{'}-1\} </tex>, <tex> bst_{i} </tex> poate fi îmbunătăţit cu valoarea <tex> bst_{k} + S_{j^{'}} </tex>. Minimul mulţimii <tex> \{bst_{k} + S_{j^{'}} : \forall k \in \{j, j+1,.., j^{'}-1\}\} </tex> este egal cu minimul expresiei <tex> \{bst_{k} : \forall k \in \{j, j+1,.., j^{'}-1\}\} + S_{j^{'}} (*) </tex>, deci, schimbând reperele, pentru maximul de pe poziţia <tex> j^{'} </tex>, dacă lungimea secvenţei care se termină în <tex> i </tex> este cel puţin <tex> i-j^{'}+1 </tex>, atunci optimul se obţine calculând rezultatul expresiei <tex> (*) </tex>. Pentru minimul pe un interval, <tex> [j, j^{'}-1] </tex> al valorile vectorului <tex> bst </tex>, putem folosi un arbore de intervale pentru <tex> O(logN) </tex> pe interogare.
 
Dar, lungimea ultimei secvenţe ce se termină în <tex> i </tex> poate fi mai mică decât <tex> i-j^{'}+1 </tex>, deci cel mult <tex> i-j^{'} </tex>. Optimul se găseşte printre elementele mulţimii <tex> \{bst_{k} + Max\{S_{k+1},..,S_{i}\} : j^{'} \le k < i\} </tex>. Dacă procedăm ca la pasul anterior vom obţine un alt indice <tex> j^{''} </tex> cu aceleaşi proprietăţi pentru secvenţa <tex> [j^{'}, i] </tex> precum <tex> j^{'} </tex> pentru secvenţa <tex> [j, i] </tex>.
 
Inductiv obţinem un şir de indici <tex> j_{0} = j < j_{1} < j_{2} < .. < j_{K} = i </tex> astfel încât <tex> S_{j_{1}} </tex> este cel mai mare element al secvenţei <tex> (j, i] </tex>, <tex> S_{j_{2}} </tex> cel mai mare element al secvenţei <tex> (j_{1}, i] </tex>, şi aşa mai departe, când <tex> j_{K} </tex> este chiar <tex> i </tex>.

== code(cpp) |
Algoritmul este: