* dacă îl decrementăm pe $j$, atunci ori $j < i - Y$ ori $MAX - MIN > Z$;
* dacă îl incrementăm pe $i$ la $i + 1$, atunci se poate întâmpla ca $j < i - Y$; cum $MAX$ nu poate decât să crească, iar $MIN$ decât să scadă, se mai poate de asemenea întâmpla ca $MAX - MIN > Z$.

Datorită proprietăţilor de mai sus, când trecem de la $i$ la $i + 1$, valoarea lui $j$ nu poate decât să crească cât timp $MAX - MIN > Z$ şi $j$ nu a depăşit poziţia $i - X$. Pentru determinarea lui $MAX$, respectiv lui $MIN$ se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(Y))$.

Datorită proprietăţilor de mai sus, când trecem de la $i$ la $i + 1$, valoarea lui $j$ nu poate decât să crească cât timp $j < i - Y$ sau $MAX - MIN > Z$ şi $j$ nu a depăşit poziţia $i - X$. Pentru determinarea lui $MAX$, respectiv lui $MIN$ se poate folosi un arbore de intervale. Complexitatea finală va fi $O(N * log{~2~}(Y))$.

Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o dată cu $j$. Destul de eficient. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului.

Cu cei doi indici $i$ şi $j$ vom accesa fiecare element din cele $N$ de cel mult $2$ ori, o dată cu $i$ şi o dată cu $j$. Să vedem cum putem îmbunătăţi complexitatea $O(log{~2~}Y)$ pentru determinarea maximului şi minimului.

Pentru fixarea ideilor să urmărim cum îl calculăm 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 în intervalul $(j, i]$, poziţia eliminată va fi {$i{~1~}$}.

_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 în intervalul $(j, i]$, poziţia eliminată va fi {$i{~1~}$}.”

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 contiguu 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 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 contiguu 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ă, programul poate arăta în felul următor: