Sfârşit.
==
Complexitatea algoritmului este $O(N^2^)$, dar pentru limitele problemei este enorm de mare.
Complexitatea algoritmului este $O(N^2^)$, dar care pentru limitele problemei este enorm.
Din pseudocodul de mai sus se vede că pentru un indice $i$ fixat, iterăm cu un alt indice $j$ pentru a găsi diferenţa maximă în modul dintre $S[i]$ şi un alt număr din intervalul $[i - D, i]$. Însă, diferenţa dintre cel mai mare număr şi cel mai mic număr este cel puţin la fel de bună ca rezultatul de la $j$-ul anterior. Astfel, pentru indicele $i$ fixat succesiv cu $1$, $2$, .., $N$, considerăm secvenţa $[i - D, i]$ în care determinăm valoarea maximă şi valoarea minimă, iar diferenţa lor o comparăm cu rezultatul cel mai bun obţinut până în acel moment.
Din pseudocodul de mai sus se vede că pentru un indice $i$ fixat, iterăm cu un alt indice $j$ pentru a găsi diferenţa maximă în modul dintre $S[i]$ şi un alt număr din intervalul $[i - D, i]$. Însă, diferenţa dintre cel mai mare număr şi cel mai mic număr este cel puţin la fel de bună decât rezultatul anterior. Astfel, pentru indicele $i$ fixat succesiv cu $1$, $2$, .., $N$, considerăm secvenţa $[i - D, i]$ în care determinăm valoarea maximă şi valoarea minimă iar diferenţa lor o comparăm cu rezultatul cel mai bun obţinut până în acel moment. Dacă considerăm o secvenţă de lungime mai scurtă, atunci este posibil să pierdem din soluţii. Un caz este când cea mai mică şi cea mai mare dintre valori se găsesc pe poziţiile $i - D$, respectiv $i$.
Pentru fixarea ideii, să urmărim cum putem determina eficient valoarea maximă din fiecare secvenţă $[i - D, i]$.
# 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 valoarea de pe poziţia $i{~1~}$ şi cea de pe poziţia $i{~2~}$ sunt candidate la maxim, la momentul curent sau în viitor.
Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir strict descrescător de numere: $T{~i~} = S[i{~1~}] > S[i{~2~}] > ... > S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] ≤ S[i{~1~}]$ şi $i - D ≤ j < i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] ≤ S[i{~2~}]$ şi $i{~1~} < j < i{~2~}$, $S[i{~3~}]$ elimină toate elementele $S[j]$, cu $S[j] ≤ S[i{~3~}]$ şi $i{~2~} < j < i{~3~}$ ş.a.m.d. De reţinut este că niciuna dintre valorile de pe poziţiile eliminate nu poate fi maximă, motiv pentru care le-am putut elimina. Şirul $T{~i~}$ are următoarele proprietăţi:
Cu această observaţie deducem că într-o secvenţă $[i - D, i]$ vom avea un şir strict descrescător de numere: $T{~i~} = S[i{~1~}] > S[i{~2~}] > ... > S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~1~}]$ şi $i - D ≤ j < i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~2~}]$ şi $i{~1~} < j < i{~2~}$, $S[i{~3~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~3~}]$ şi $i{~2~} < j < i{~3~}$ ş.a.m.d. De reţinut este că niciuna dintre valorile de pe poziţiile eliminate nu poate fi maximă, motiv pentru care le-am putut elimina.
Şirul $T{~i~}$ are următoarele proprietăţi:
* se termină pe poziţia curentă, adică are loc egalitatea $i{~K~} = i$ întrucât poziţia $i$ nu va fi eliminată de nicio altă poziţie;
* valoarea căutată, adică maximul dintre numerele din secvenţă, se găseşte pe prima poziţie.
Când vom avansa la secvenţa următoare, $[i - D + 1, i + 1]$, vom forma şirul $T{~i+1~}$ ştergând 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~}]$ ...
Când vom avansa la secvenţa următoare, $[i - D + 1, i + 1]$, vom forma şirul $T{~i+1~}$ ştergând 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 $T{~i~}$ poate fi păstrat prin intermediul şirului de indici $i{~1~} < i{~2~} < ... < i{~K~}$. Operaţiile pe acest şir se efectuează doar pe la cele două capete, aşadar poate fi implementat cu ajutorul unui $deque$.
Şirul $T{~i~}$ poate fi păstrat prin intermediul şirului de indici $i{~1~} < i{~2~} < ... < i{~K~}$. Acest şir de indici este continuu iar operaţiile de mai sus se efectuează doar pe la cele două capete. Rezultă că şirul poate fi implementat cu ajutorul unui deque.
Pentru $S[] = {5, 9, 4, 7, 4, 1}$ şi $D = 3$ obţinem următoarele stări ale unui deque:
* <tex> \langle \widehat{5\ [1]} \rangle </tex>;
* <tex> \langle 5\ [1] \rangle \Leftarrow 9\ [2] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]} \rangle </tex>;
* <tex> \langle 9\ [2] \rangle \Leftarrow 4\ [3] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 4\ [3] \rangle </tex>;
* <tex> \langle 9\ [2],\ 4\ [3] \rangle \Leftarrow 7\ [4] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 7\ [4] \rangle </tex>;
* <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>;
* <tex> \langle \widehat{5\ [1]} \rangle; </tex>
* <tex> \langle 5\ [1] \rangle \Leftarrow 9\ [2] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]} \rangle; </tex>
* <tex> \langle 9\ [2] \rangle \Leftarrow 4\ [3] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 4\ [3] \rangle; </tex>
* <tex> \langle 9\ [2],\ 4\ [3] \rangle \Leftarrow 7\ [4] </tex> de unde se obţine <tex> \langle \widehat{9\ [2]},\ 7\ [4] \rangle; </tex>
* <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$ este adăugat şi şters cel mult o dată din deque, complexitatea finală este $O(N)$.
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
