Să vedem cum putem îmbunătăţi complexitatea $O(log N)$ pentru determinarea maximului şi minimului. Mai jos vom vedea algoritmul pentru a-l calcula pe $MAX$, cazul lui $MIN$ fiind similar. Observaţia care ne ajută în multe probleme pentru reducerea complexităţii de la $O(log N)$ la $O(1)$ este, asemănător problemei precedente, următoarea:

_Observaţie_: Fie $[j, i]$ un interval de interes şi $i{~1~}$ şi $i{~2~}$ doi indici astfel încât $j &le; i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~1~}] &le; S[i{~2~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Aşadar putem renunţa la $i{~1~}$ pentru etapele următoare, eliminându-l. 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 de forma $[j, i]$. În schimb, când $i{~1~}$ va fi eliminat, $i{~2~}$ are şansa să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, vom păstra ambele poziţii şi pentru paşii următori.

_Observaţie_: Fie $[j, i]$ un interval de interes şi $i{~1~}$ şi $i{~2~}$ doi indici astfel încât $j &le; i{~1~} < i{~2~} &le; i$. Atunci, dacă $S[i{~1~}] < S[i{~2~}]$ poziţia $i{~2~}$ va fi întotdeauna preferată poziţiei $i{~1~}$ atâta timp cât cele două poziţii vor fi în acelaşi interval de interes. Aşadar putem renunţa la $i{~1~}$ pentru etapele următoare, eliminându-l. Dacă, însă, $S[i{~1~}] &ge; 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 de forma $[j, i]$. În schimb, când $i{~1~}$ va fi eliminat, $i{~2~}$ are şansa să fie un candidat la $MAX$ dintre restul elementelor de la dreapta sa. În acest caz, vom păstra ambele poziţii şi pentru paşii următori.

Rezultă din această observaţie, analog 'problemei anterioare':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 extragem $MAX$ ca fiind $S[i{~1~}]$. Folosind iarăşi structura de date $deque$, complexitatea algoritmului va fi $O(N)$.

Rezultă din această observaţie, analog 'problemei anterioare':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~}] &ge; S[i{~2~}] &ge; ... &ge; S[i{~k~}]$, din care extragem $MAX$ ca fiind $S[i{~1~}]$. Folosind iarăşi structura de date $deque$, complexitatea algoritmului va fi $O(N)$.

În pseudocod, algoritmul va arăta în felul următor:

Sfârşit;
Algoritmul este:

    lg = 0;

    lg = 0; j = 1;

    pentru i = 1, N execută

        // funcţia min(a, b) întoarce true dacă a <= b

        // funcţia min(a, b) întoarce true dacă a < b

        push(min_deq, i, min);

        // funcţia max(a, b) întoarce true dacă a >= b

        // funcţia max(a, b) întoarce true dacă a > b

        push(max_deq, i, max);
        cât timp ((j <= i - Y sau query(max_deq, j) - query(min_deq, j) > Z) şi j <= i - X + 1) execută
            j = j + 1;

        // (j, i] este intervalul candidat la soluţia optimă pentru poziţia i
        dacă (j <= i - X) şi (query(max_deq, j) - query(min_deq, j) <= Z) atunci
            dacă (lg >= i - j) atunci
                lg = i - j, start = j + 1, stop = i;

        // [j, i] este intervalul candidat la soluţia optimă pentru poziţia i
        dacă (j <= i - X + 1) şi (query(max_deq, j) - query(min_deq, j) <= Z) atunci
            dacă (lg >= i - j + 1) atunci
                lg = i - j + 1, start = j, stop = i;

    sfârşit_pentru
    dacă (lg > 0) atunci

        scrie lg, start, stop;

        soluţia este (lg, start, stop);

    altfel

        scrie -1;

        nu există soluţie;

Sfârşit.
==