Voi prezenta mai jos o rafinare a soluţiei în trei paşi.

Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom determina pentru aceasta secvenţa cerută, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $O(log{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu soluţia finală. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}Y)$.

Prima rezolvare se găseşte uşor, deoarece nu facem decât să urmărim textul: pentru fiecare poziţie $i$ fixată ({$i$} ia valorile $1$, $2$, .., $N$ succesiv) vom considera toate secvenţele candidate la rezultatul final, adică vom plimba un $j$ între poziţiile $i - Y$ şi $i - X$. Pentru un interval $(j, i]$ vom determina $MAX$ şi $MIN$ în $O(log{~2~}N)$ cu un arbore de intervale, iar daca diferenţa dintre acestea nu depăşeşte $Z$ vom compara cu rezultatul obţinut până în acel moment. Complexitatea finală va fi $O(N * (Y - X) * log{~2~}N)$.

Să presupunem că pentru poziţia curentă $i$, l-am găsit pe $j$ cât mai mic cuprins între $i - Y$ şi $i - X$ astfel încât secvenţa $(j, i]$ este candidată la soluţie. Ce proprietăţi are $j$?

Cum se cere secvenţa de lungime maximă, pentru fiecare poziţie $i$ trebuie găsit indicele $j$ cât mai mic cuprins între $i - Y$ şi $i - X$ astfel încât secvenţa $(j, i]$ să fie candidată la soluţie. Ce proprietăţi are indicele $j$?

* $i - Y ≤ j ≤ i - X$ şi $MAX - MIN ≤ Z$;
* dacă îl incrementăm pe $j$ la $j + 1$ atunci dacă $j ≤ i - X$ cu siguranţă $MAX - MIN ≤ Z$ şi astfel soluţia va fi mai scurtă;
* dacă îl decrementăm pe $j$, atunci ori $j < i - Y$ ori $MAX - MIN > Z$;
* dacă îl incrementăm pe $i$ la $i + 1$, atunci se poate întâmpla ca $j < i - Y$; cum $MAX$ nu poate decât să crească, iar $MIN$ decât să scadă, se mai poate de asemenea întâmpla ca $MAX - MIN > Z$.

Datorită proprietăţilor de mai sus, când trecem de la $i$ la $i + 1$, valoarea lui $j$ nu poate decât să crească cât timp $j < i - Y$ sau $MAX - MIN > Z$ şi $j$ nu a depăşit poziţia $i - X$. Pentru determinarea lui $MAX$, respectiv lui $MIN$ se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(Y))$.

Datorită proprietăţilor de mai sus, când trecem de la $i$ la $i + 1$, valoarea lui $j$ nu poate decât să crească cât timp $j < i - Y$ sau $MAX - MIN > Z$ şi $j$ nu a depăşit poziţia $i - X$. Pentru determinarea lui $MAX$, respectiv lui $MIN$ pe fiecare interval $(j, i]$, cu proprietăţile de mai sus, se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(N))$.

Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o dată cu $j$. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului.

Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o dată cu $j$. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}N)$ pentru determinarea maximului şi minimului.

Pentru fixarea ideilor să urmărim cum îl vom calcula pe $MAX$. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log{~2~}N)$ la $O(1)$ amortizat este următoarea:

Pentru fixarea ideilor să urmărim cum îl vom calcula pe $MAX$. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log{~2~}N)$ la $O(1)$ amortizat este, asemănător problemei precedentă, următoarea:

_Observaţie_: Fixăm $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi ambele în intervalul $(j, i]$, poziţia eliminată va fi $i{~1~}$. Dacă însă $S[i{~1~}] > S[i{~2~}]$, atunci poziţia $i{~1~}$ va umbri poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ va fi eliminat, atunci e posibil ca $i{~2~}$ să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, nu putem afirma nimic şi vom păstra cele două poziţii.

_Observaţie_: Fie $(j, i]$ un interval de interes şi $i{~1~}$ şi $i{~2~}$ astfel încât $j < i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~2~}] > S[i{~1~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Când $i{~1~}$ şi $i{~2~}$ nu vor mai fi ambele în acelaşi interval poziţia eliminată va fi $i{~1~}$. Dacă însă $S[i{~1~}] > S[i{~2~}]$, atunci poziţia $i{~1~}$ va umbri poziţia $i{~2~}$ atâta timp cât cele două poziţii vor fi în intervalul $(j, i]$. Când $i{~1~}$ va fi eliminat, atunci e posibil ca $i{~2~}$ să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, nu putem afirma nimic şi vom păstra cele două poziţii.

Rezultă din această observaţie, precum în 'problema anterioară':deque-si-aplicatii#problema-2, că în intervalul $(j, i]$ se va forma un şir de poziţii $i{~1~} < i{~2~} < .. < i{~k~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$, din care obţinem că $MAX$ este egal cu $S[i{~1~}]$. Când îl vom incrementa pe $i$ la $i + 1$ vom şterge din poziţiile $i{~k~}$, $i{~k-1~}$, ... atâta timp cât $S[i + 1]$ este mai mare decât valorile de pe aceste poziţii, şi vom şterge $i{~1~}$, $i{~2~}$, ... atâta timp cât aceste poziţii sunt mai mici sau egale decât $j'$. Indicele $j'$ este noul optim pentru poziţia $i + 1$. Proprietatea şirului de poziţii $i{~1~}, i{~2~}, .., i{~k~}$ este că se reprezintă ca un şir continuu de numere care permite inserarea elementelor prin dreapta şi ştergerea prin stânga, adică se adaugă elemente la tail şi se şterg elemente de la head. Îl putem deci reprezenta printr-un deque. Complexitatea $O(1)$ amortizat provine de la faptul că fiecare poziţie dintre cele $N$ nu trece decât o singură dată prin deque şi este şters tot cel mult o singură dată.

Rezultă din această observaţie, analog 'problemei anterioare':deque-si-aplicatii#problema-2, că în intervalul $(j, i]$ se va forma un şir de poziţii $i{~1~} < i{~2~} < .. < i{~k~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$, din care obţinem că $MAX$ este egal cu $S[i{~1~}]$. Observaţia ne arată că indicele $i{~1~}$ elimină toate valorile mai mici decât $S[i{~1~}]$ aflate în intervalul $(j, i{~1~})$, indicele $i{~2~}$ elimină toate valorile mai mici decât $S[i{~2~}]$ aflate în intervalul $(i{~1~}, i{~2~})$ ş.a.m.d. Când îl vom incrementa pe $i$ la $i + 1$ vom şterge din poziţiile $i{~k~}$, $i{~k-1~}$, ... atâta timp cât $S[i + 1]$ este mai mare decât valorile de pe aceste poziţii, şi vom şterge $i{~1~}$, $i{~2~}$, ... atâta timp cât aceste poziţii sunt mai mici sau egale decât $j'$. Indicele $j'$ este noul optim pentru poziţia $i + 1$. Proprietatea şirului de poziţii $i{~1~}, i{~2~}, .., i{~k~}$ este că se reprezintă ca un şir continuu de numere care permite inserarea elementelor prin dreapta şi ştergerea prin stânga, adică se adaugă elemente la tail şi se şterg elemente de la head. Îl putem deci reprezenta printr-un deque. Complexitatea $O(1)$ amortizat provine de la faptul că fiecare poziţie dintre cele $N$ nu trece decât o singură dată prin deque şi este şters tot cel mult o singură dată.

În practică, pseudocodul poate arăta în felul următor:

* <tex> bst_{i,c} = Min\ \{\ Minim(bst_{j,0},\ bst_{j,1}) - sum_{j,c}\ :\ i - K \le j \le i - 1\ \} + sum_{i,c} + T; </tex>

Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} < T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} < T_{i_{2},c} <  .. < T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.

Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} < T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe, după cum am arătat în problemele anterioare, că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} < T_{i_{2},c} <  .. < T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.

După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări prin dreapta (tail) şi ştergeri prin stânga (head). Şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va trece o singură dată prin deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.