În practică, programul poate arăta în felul următor:
== code(cpp) |
// S şirul de numere iniţial şi N lungimea sa
// ...
Subalgoritmul push_in(deque, întreg p, funcţia fct) este:
cât timp (!deque.empty() şi fct(S[p], S[deque.back()])) execută
deque.pop_back();
deque.push_back(p);
Sfârşit;
Funcţia query(deque, întreg j) este:
cât timp (!deque.empty() şi deque.front() ≤ j) execută
deque.pop_front();
return S[deque.front()];
Sfârşit;
Algoritmul este:
lg = 0;
pentru i = 1, N execută
// funcţia min(a, b) întoarce true dacă a < b
inserează(min_deq, i, min);
// funcţia max(a, b) întoarce true dacă a > b
inserează(max_deq, i, max);
cât timp ((j < i - Y sau query(max_deq, j) - query(min_deq, j) > Z) şi j < i - X) 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;
sfârşit_pentru
dacă (lg > 0) then
scrie lg, start, stop;
altfel
scrie -1;
Sfârşit.
deque <int> min_deq, max_deq;
typedef int (*PF)(const int , const int ) ;
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, const int p, PF compare) {
for (; !deq.empty() && compare(S[p], S[deq.back()]); deq.pop_back()) ;
deq.push_back(p);
}
int query(deque <int>& deq, const int j) {
for (; !deq.empty() && deq.front() <= j; deq.pop_front()) ;
return S[deq.front()];
}
int main(void) {
// ...
for (int i = 1; i <= N; ++ 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 ++;
// (j, i] este intervalul candidat la soluţia pentru pozitia i
if (j <= i - X) if (query(max_deq, j) - query(min_deq, j) <= Z)
// compară cu rezultatul de până acum
}
// ...
}
==
Complexitatea finală va fi $O(N)$.