[C++, programare dinamică] Problema subșirului crescător maximal

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Considerăm un vector A cu N elemente numere întregi. Un subșir a lui A este o secvență de elemente nu neapărat consecutive ale lui A, dar a căror ordine relativă în A este păstrată. Un subșir crescător al lui A este un subșir al lui A ale cărui elemente sunt ordonate crescător. Un subșir crescător maximal este un subșir crescător la care nu se mai pot adăuga elemente fără a strica proprietatea de subșir crescător. Se cere determinarea celui mai lung subșir crescător maximal al vectorului A.

Datele de intrare se citesc din fișierul subsir.in. In fișierul subsir.out se va afișa pe prima linie lungimea lg a celui mai lung subșir crescător maximal găsit, iar pe următoarea linie se vor afișa valorile (în număr de lg) care constituie un astfel de subșir. Se poate afișa orice soluție dacă există mai multe.

Exemplu:

subsir.in	subsir.out
10 6 3 8 9 1 2 10 4 -1 11	5 6 8 9 10 11

Problema admite o rezolvare prin programare dinamică în timp O(N²), dar și o rezolvare greedy în timp O(N·log N). Vom prezenta ambele rezolvări.

Rezolvarea prin programare dinamică presupune găsirea unei formule de recurență care fie va furniza direct răspunsul problemei, fie va fi doar un pas intermediar în rezolvarea problemei. In acest caz, putem găsi o formulă de recurență pentru Lg care va conduce direct la calcularea acestei valori. Raționamentul este unul similar cu cel de la problema anterioară. Fie L[i] = lungimea celui mai lung subșir crescător maximal care se termină e poziția i. Inițial vom considera L[i] = 1 pentru fiecare 1 ≤ i ≤ N. Evident, L[1] va rămâne întotdeauna 1, deoarece singurul subșir al unui vector cu un singur element este însuși acel vector.

Să presupunem acum că avem calculate valorile L[1], L[2], ..., L[k] pentru un k < N. Ne propunem să calculăm L[k + 1]. Folosind definiția lui L, ne propunem așadar să calculăm lungimea celui mai lung subșir crescător maximal care se termină pe poziția k + 1, știind lungimile celor mai lungi subșiruri crescătoare maximal care se termină pe pozițiile 1, 2, ..., k. Stiind aceste valori, este evident că pentru a maximiza lungimea subșirului care se termină pe poziția k + 1 trebuie adăugat A[k + 1] unui subșir maximal care se termină pe o poziție j < k + 1, pentru care L[j] are valoarea maximă și pentru care A[j] < A[k + 1], deoarece subșirul trebuie să fie crescător. Așadar obținem recurența:

    L[1] = 1
    L[i] = 1 + max{L[j] | A[j] < A[i]} sau 1 dacă mulțimea respectivă e vidă, unde 1 ≤ j < i.

( n.e. Trebuie adăugat A[k + 1] ca o continuare la subșirul crescător maximal de lungime maximă descoperit până la k, acest subșir se termină pe o poziție j < k + 1 și e necesar ca A[j] < A[k + 1]. )

Timpul O(N²) rezultă din faptul că pentru fiecare i trebuie să determinăm minimul subsecvenței [1, i - 1], rezultând un număr pătratic de operații. Valoarea lg este dată de valoarea maximă din vectorul L.


Pentru determinarea valorilor care fac parte din subșirul crescător maximal vom folosi un vector P unde P[i] = poziția ultimului element care a intrat în calculul lui L[i] sau 0 dacă nu există. In alte cuvinte, dacă L[i] = 1 + max{L[j] | A[j] <  A[i]} = 1 + L[max], 1 ≤ j < i, atunci vom avea P[i] = max.


Vom evidenția în continuare modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	1	1	1	1	1	1	1	1	1	1
P[i]	0	0	0	0	0	0	0	0	0	0

La pasul i = 2 căutăm poziția max a celui mai mare element din subsecvența [1, 1] a vectorului L pentru care A[max] < A[2]. Nu se găsește nicio astfel de poziție, așa că totul rămâne neschimbat.

La pasul i = 3 căutăm același max din subsecvența [1, 2] a vectorului L pentru care are loc A[max] < A[3]. Putem alege de data aceasta fie max = 1, fie max = 2, ambele poziții respectând condițiile impuse. Vom alege max = 1. Așadar, L[3] devine L[max]+1 = L[1]+1 = 2, iar P[3] devine max, adică 1. Am marcat cu roșu actualizările:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	1	1	2	1	1	1	1	1	1	1
P[i]	0	0	1	0	0	0	0	0	0	0

Se procedează în acest fel până la completarea vectorilor L și P. Forma lor finală este prezentată mai jos. Este ușor de verificat corectitudinea calculării acestor vectori conform definiției lor.

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	1	1	2	1	3	1	4	3	1	5
P[i]	0	0	1	3	0	5	4	6	0	7

Am marcat mai sus coloanele care identifică o soluție optimă. Vom explica în continuare cum putem folosi vectorul P pentru a obține valorile soluției optime. Fie sol poziția celui mai mare element din vectorul L. In acest caz, sol = 10. Este clar că ultima valoare din subșirul crescător maximal este atunci A[10]. Deoarece P[i] reprezintă ultima valoare care a intrat în calcului lui L[i] (sau predecesorul lui i), P[10] reprezintă poziția penultimei valori a subșirului crescător maximal găsit. Atunci A[ P[10] ] reprezintă penultima valoare a soluției. Mergând în continuare cu acest raționament, A[ P[ P[10] ] ] va reprezenta antepenultima valoare și așa mai departe până când ajungem la o valoare k pentru care P[k] = 0. Când acest lucru se întâmplă, am găsit prima valoare a subșirului soluție.

Vom folosi așadar o funcție recursivă care va reconstitui soluția folosind vectorul P. Acest vector se numește vector de predecesori, iar ideea folosită în construcția sa poate fi aplicată la orice problemă de programare dinamică la care se cere afișarea unor obiecte care constituie un optim cerut. Prezentăm întregul program care rezolvă problema.

Această rezolvare poate fi optimizată folosind structuri de date avansate, cum ar fi arbori de intervale sau arbori indexați binar, dar aceste structuri nu vor fi prezentate în cadrul acestui capitol și nu sunt nici cea mai bună metodă de a rezolva optim această problemă.

Vom prezenta în continuare o rezolvare optimă cu timpul de execuție O(N · log N) care nu presupune decât noțiuni algoritmice elementare.


Vom considera A ca fiind vectorul citit și vom folosi încă doi vectori L și P, dar care nu vor avea aceeași semnificație ca până acum.

Mai întâi inițializăm vectorul L cu valoarea infinit. Aplicăm apoi următorul algoritm:

• Pentru fiecare i de la 1 la N execută
• Suprascrie A[i] peste cel mai mic element din L, dar care este strict mai mare decât A[i]. (1)
• Fie k poziția peste care a fost suprascris A[i]. P[i] ia valoarea k.
• Lungimea vectorului L (făcând abstracție de pozițiile marcate cu infinit) reprezintă lungimea celui mai lung subșir crescător maximal.
• Fie lg lungimea vectorului L. Pentru a reconstitui soluția, se caută în vectorul P poziția ultimei apariții a valorii lg. Fie această poziție k_lg. Se caută apoi ultima apariție a valorii lg - 1, dar care apare înainte de poziția k_lg. Aceasta va fi așadar pe o poziție k_{lg - 1} < k_lg. Se procedează similar pentru valorile lg - 2, lg - 3, ..., 2, 1. Soluția va fi dată de subșirul: A[k₁], A[k₂], ..., A[k_lg]. Putem implementa reconstituirea tot recursiv.

La pasul (1), dacă A[i] este mai mare decât toate elementele diferite de infinit din L, atunci A[i] se va suprascrie peste cea mai din stânga valoare egală cu infinit. Putem implementa acest pas eficient în timp O(log N) folosind o căutare binară.

Să prezentăm modul de execuție al algoritmului pe exemplul dat. Inițial avem:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	inf	inf	inf	inf	inf	inf	inf	inf	inf	inf
P[i]

La pasul i = 1, se suprascrie A[1] = 6 peste cea mai mică valoare din L, dar care este strict mai mare decât 6. Singura posibilitate este să suprascriem elementul A[1] peste primul inf. In P[1] vom reține 1:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	6	inf	inf	inf	inf	inf	inf	inf	inf	inf
P[i]	1

La pasul i = 2, A[2] = 3 se va suprascrie peste L[1] = 6, iar P[2] devine 1:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	3	inf	inf	inf	inf	inf	inf	inf	inf	inf
P[i]	1	1

A[3] se va suprascrie peste L[2], iar P[3] va deveni 2. Se procedează în acest mod pentru fiecare element din A, iar forma finală a vectorilor este:

i	1	2	3	4	5	6	7	8	9	10
A[i]	6	3	8	9	1	2	10	4	-1	11
L[i]	-1	2	4	10	11	inf	inf	inf	inf	inf
P[i]	1	1	2	3	1	2	4	3	1	5

Lungimea lg este așadar 5, deoarece există 5 elemente diferite de inf în L. Soluția este dată de A[2], A[3], A[4], A[7] și A[10].

Prezentăm în continuare implementarea acestei metode de rezolvare.

Deși acest algoritm este mai eficient, spre deosebire de metoda clasică, nu poate fi adaptat la toate variațiunile problemei.

Exercițiu: scrieți un program care determină cel mai scurt subșir crescător maximal și altul care determină numărul de subșiruri crescătoare maximal.