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]|;

Algoritmul este:
    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;

sfârşit_pentru;
return ret;

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

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~}] &gt; S[i{~2~}] &gt; ... &gt; S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~1~}]$ şi $i - D &le; j &lt; i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~2~}]$ şi $i - D &le; j &lt; 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.

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~}] &gt; S[i{~2~}] &gt; ... &gt; S[i{~K~}]$, unde $S[i{~1~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~1~}]$ şi $i - D &le; j &lt; i{~1~}$, $S[i{~2~}]$ elimină toate elementele $S[j]$, cu $S[j] < S[i{~2~}]$ şi $i - D &le; j &lt; i{~2~}, j != i{~1~}$ dar fără poziţia $i{~1~}$ ş.a.m.d.
Şirul $T{~i~}$ are următoarele proprietăţi:

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ă.

* 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.

Ş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.

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~}$ care 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:

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:

_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 mai importantă decât poziţia $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_: 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.

Rezultă din această observaţie că în intervalul $(j, i]$ poziţiile importante vor fi $j < i{~1~} < i{~2~} < .. < i{~k~} <= i$ astfel încât $S[i{~1~}] > S[i{~2~}] > .. > S[i{~k~}]$. Astfel, $MAX$ va fi $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 important, adică 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, 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 important, adică 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: