h3. Soluţie:

Soluţia nu este greu de intuit. Dacă vom considera indicii $1$, $2$, .. , $N$ succesiv va trebuie ca pentru fiecare secvenţă $(i - D, i]$ să determinăm valoarea maximă şi pe cea minimă, iar diferenţa lor să o comparăm cu rezultatul obţinut până în acel moment. Pentru fixarea ideilor, să urmărim cum putem determina valoarea maximă din fiecare secvenţă $(i - D, i]$.

Soluţia nu este greu de intuit. Dacă vom considera indicii $1$, $2$, ... , $N$ succesiv, va trebui ca pentru fiecare secvenţă $[i - D, i]$ să determinăm valoarea maximă şi pe cea minimă, iar diferenţa lor să o comparăm cu rezultatul cel mai bun obţinut până în acel moment. Pentru fixarea ideii, să urmărim cum putem determina eficient valoarea maximă din fiecare secvenţă $[i - D, i]$.

_Observaţie_: „Fie $i{~1~}$, $i{~2~}$ doi indici astfel încât $i - D < i{~1~} < i{~2~} ≤ i$.

_Observaţie_: Fie $i{~1~}$, $i{~2~}$ doi indici astfel încât $i - D ≤ i{~1~} < i{~2~} ≤ i$.

# Dacă $S[i{~1~}] < S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervalul $(i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţia $i{~1~}$. Când unul din indici nu va mai fi în acest interval, cel expediat va fi $i{~1~}$ şi, astfel, $i{~2~}$ rămâne în continuare preferat.
# Dacă $S[i{~1~}] > S[i{~2~}]$ atunci îl vom păstra pe $i{~2~}$, deoarece este candidat la maxim în viitor.”

# Dacă $S[i{~1~}] ≤ S[i{~2~}]$ atunci, cât timp cei doi indici vor fi în intervale de tipul $[i - D, i]$, valoarea de pe poziţia $i{~2~}$ va fi întotdeauna preferată valorii de pe poziţia $i{~1~}$. Când se ajunge la un interval care nu-l mai conţine pe $i{~1~}$, $i{~2~}$ rămâne în continuare preferat.
# Dacă $S[i{~1~}] > S[i{~2~}]$ atunci şi $i{~1~}$ şi $i{~2~}$ sunt candidaţi la maxim, la momentul curent sau în viitor.

Cu această observaţie deducem că într-o secvenţă $(i - D, i]$ vom avea un şir $i{~1~} < i{~2~} < ... < i{~K~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > ... > S[i{~K~}]$. Când vom avansa la secvenţa următoare, $(i - D + 1, i + 1]$, vom şterge din indicii $i{~1~}$, $i{~2~}$... atâta timp cât nu se găsesc în intervalul curent şi vom şterge din poziţiile $i{~K~}$, $i{~K-1~}$... cât timp $S[i + 1] > S[i{~K~}]$, $S[i + 1] > S[i{~K-1~}]$... adică cât timp se îndeplineşte primul punct din observaţia anterioară.

Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir $i{~1~} < i{~2~} < ... < i{~K~}$ astfel încât $S[i{~1~}] > S[i{~2~}] > ... > S[i{~K~}]$. Când vom avansa la secvenţa următoare, $[i - D + 1, i + 1]$, vom şterge din indicii $i{~1~}$, $i{~2~}$... atâta timp cât nu se găsesc în intervalul curent şi vom şterge din poziţiile $i{~K~}$, $i{~K-1~}$... cât timp $S[i + 1] > S[i{~K~}]$, $S[i + 1] > S[i{~K-1~}]$... adică cât timp se îndeplineşte primul punct din observaţia anterioară.

Şirul $i{~1~} < i{~2~} < ... < i{~K~}$ este continuu iar operaţiile se efectuează doar pe la cele două capete. Rezultă că şirul poate fi implementat cu ajutorul unui deque.

* <tex> 9\ [2] \Leftarrow \langle 7\ [4] \rangle \Leftarrow 4\ [5] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5] \rangle; </tex>
* <tex> \langle 7\ [4],\ 4\ [5] \rangle \Leftarrow 1\ [6] </tex> de unde se obţine <tex> \langle \widehat{7\ [4]},\ 4\ [5],\ 1\ [6] \rangle; </tex>

Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque, complexitatea finală este $O(N)$ amortizat.

Cum fiecare indice din $1$, $2$, .., $N$ trece cel mult o dată prin deque, complexitatea finală este $O(N)$.

h2(#problema-3). 3. 'Şir':problema/sir