h3. Soluţie:

Soluţia nu este greu de intuit. Considerăm indicii succesiv $1$, $2$, .. , $N$. 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 e greu de intuit. Considerăm indicii succesiv $1$, $2$, .. , $N$. 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]$.

_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 din 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ţiei $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.”

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 indici $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.

p=. !deque-si-aplicatii?vila22.png 60%!

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)$ amortizat.

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