j = j + 1;
        // [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

            dacă (lg <= i - j + 1) atunci

                lg = i - j + 1, start = j, stop = i;
    sfârşit_pentru

Sfârşit.
==

h2(#problema-4). 4. 'Platforma':http://campion.edu.ro/problems/3/509/platforma_ro.htm (.campion, 2009)

h2(#problema-4). 4. 'Platforma':http://campion.edu.ro/arhiva/index.php?page=problem&action=view&id=85 (.campion, 2009)

bq. Se dă o matrice $P$ de dimensiuni $M x N$ cu elemente numere întregi. Se defineşte valoarea maximă dintr-un dreptunghi de dimensiuni $R x C$ ca fiind valoarea maximă dintre elementele aflate în acel dreptunghi.
Cerinţă: Să se găsească un dreptunghi de dimensiuni $R x C$ cu valoarea maximă minimă.

Notez în continuare, pentru uşurinţă în scriere, <tex> T_{j,c} = Min(bst_{j,0}, bst_{j,1}) - sum_{j,c} </tex>. Să fixăm doi indici <tex> i_{1} </tex> şi <tex> i_{2} </tex>, astfel încât <tex> i - K \le i_{1} < i_{2} \le i - 1 </tex>. Dacă <tex> T_{i_{1},c} > T_{i_{2},c} </tex> atunci întotdeauna poziţia <tex> i_{2} </tex> va fi preferată poziţiei <tex> i_{1} </tex>. Când cele două nu se vor mai afla ambele în intervalul <tex> [i - K, i - 1] </tex>, poziţia eliminată va fi poziţia <tex> i_{1} </tex>. Dacă <tex> T_{i_{1},c} \le T_{i_{2},c} </tex>, atunci nu putem decide care poziţie este mai bună în viitor, aşa că le vom păstra pe ambele. Rezultă mai departe, după cum am arătat în problemele anterioare, că în intervalul <tex> [i - K, i - 1] </tex> vom avea o serie de indecşi candidaţi la minim <tex> i - K \le i_{1} < i_{2} < \ldots < i_{n} \le i - 1 </tex> astfel încât <tex> T_{i_{1},c} \le T_{i_{2},c} \le  ... \le T_{i_{n},c} </tex>. Mai departe, găsim <tex> bst_{i,c} = T_{i_{1},c} + sum_{i,c} + T </tex>. Urmează să îl introducem şi pe <tex> T_{i,c} </tex> în şirul de indecşi de mai sus, el fiind egal cu <tex> Minim(bst_{i,0}, bst_{i,1}) - sum_{i,c} </tex>. Acest lucru se va face în felul următor: se vor elimina din <tex> i_{n}, , i_{n-1}, \ldots </tex> atâta timp cât <tex> T_{i_{n},c} > T_{i,c} </tex>, <tex> T_{i_{n-1},c} > T_{i,c} \ldots </tex> adică atâta timp cât poziţia <tex> i </tex> este preferată lui <tex> i_{n}, i_{n-1}, \ldots </tex>. Fiind la poziţia <tex> i + 1 </tex>, intervalul se va transforma în <tex> [i - K + 1, i] </tex>, aşadar, vom mai elimina din primii indici <tex> i_{1}, i_{2}, \ldots </tex> atâta timp cât <tex> i_{1} < i - K + 1, i_{2} < i - K + 1, \ldots </tex>.

După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări şi ştergeri pe la capete ($head$ şi $tail$), şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va fi adăugat şi şters cel mult o singură dată din deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.

După cum am arătat şi la problema precedentă, acest şir de indecşi <tex> i_{1}, i_{2}, \ldots, i_{n} </tex> are proprietatea că este un şir continuu de numere care admite inserări şi ştergeri pe la capete ({$head$} şi {$tail$}), şir ce poate fi reprezentat printr-un deque. Cum fiecare index dintre <tex> 1, 2, \ldots, N </tex> va fi adăugat şi şters cel mult o singură dată din deque, complexitatea soluţiei va fi <tex> O(N) </tex> pentru fiecare camion, deci <tex> O(Q * N) </tex> în total.

Iată şi o sursă scurtă, clară şi eficientă pentru această problemă:

* 'Gard':problema/gard, _ONI, 2002_
* 'Ghiozdan':problema/ghiozdan
* 'Cover':problema/cover, _Baraj ONI, 2007_

* 'Secvdist':problema/secvdist

h2(#bibliografie). Bibliografie