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.

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: „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ă. Complexitatea finală va fi $O(N)$.

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: „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ă.
 
În practică, programul poate arăta în felul următor:
 
== code(cpp) |
#include <fstream>
#include <deque>
#include <vector>
#include <algorithm>
 
using namespace std;
 
const char iname[] = "sir.in";
const char oname[] = "sir.out";
 
typedef int (*PF)(const int& , const int& ) ;
 
deque <int> min_deq, max_deq;
 
vector <int> V;
 
 
int min_fct(const int& a, const int& b) { return a < b; }
 
int max_fct(const int& a, const int& b) { return a > b; }
 
void push_in(deque <int>& deq, int& p, PF compare) {
    for (; !deq.empty() && compare(V[p], V[deq.back()]); deq.pop_back()) ;
    deq.push_back(p);
}
 
int query(deque <int>& deq, const int& first) {
    for (; !deq.empty() && deq.front() <= first; deq.pop_front()) ;
    return V[deq.front()];
}
 
int main(void)
{
    ifstream in(iname);  ofstream out(oname);
    int N, X, Y, Z;
    int length = 0, start = 0, stop = 0;
 
    int j = 0;
 
    in >> N >> X >> Y >> Z;
    V.resize(N + 1);
    for (int i = 1; i <= N; ++ i) {
        in >> V[i];
        // (j, i] este intervalul candidat la solutia pentru pozitia i;
        push_in(min_deq, i, min_fct);
        push_in(max_deq, i, max_fct);
 
        while ((j < i - Y || query(max_deq, j) - query(min_deq, j) > Z) && j < i - X)
            j ++;
 
        if (j <= i - X) if (query(max_deq, j) - query(min_deq, j) <= Z)
            if (i - j >= length)
                length = i - j, start = j + 1, stop = i;
    }
 
    if (length > 0)
        out << length << " " << start << " " << stop << "\n";
    else
        out << -1;
 
    in.close(), out.close();
    return 0;
}
==
 
Complexitatea finală va fi $O(N)$.

h3. 'Trans':problema/trans (ONI 2004)