h3. Soluţie:
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]$.
Soluţia simplă constă în procesarea tuturor perechilor de numere care se găsesc pe poziţii cu diferenţa în modul mai mică sau egală decât $D$.
== code(cpp) |
ret = 0;
pentru i = 1, N execută
pentru j = Max(1, i - D), i execută
dacă ret < |S[i] - S[j]| atunci
ret = |S[i] - S[j]|;
sfârşit_pentru;
sfârşit_pentru;
return ret;
==
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]$. Maximul dintre diferenţa celui mai mare număr şi $S[i]$, şi diferenţa dintre $S[i]$ şi cel mai mic număr, este rezultatul maxim obţinut pentru poziţia curentă $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]$.
_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 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 $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 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 - D ≤ j < i{~2~}, j != i{~1~}$ dar fără poziţia $i{~1~}$ ş.a.m.d. Ş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, iar valoarea maximă 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 ş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.
