subsir.in
|
subsir.out
|
10
6 3 8 9 1 2 10 4 -1 11
|
5
6 8 9 10 11
|
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(N2) 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 klg. Se caută apoi ultima apariție a valorii lg – 1, dar care apare înainte de poziția klg. Aceasta va fi așadar pe o poziție klg – 1 < klg. Se procedează similar pentru valorile lg – 2, lg – 3, …, 2, 1. Soluția va fi dată de subșirul: A[k1], A[k2], …, A[klg]. Putem implementa reconstituirea tot recursiv.
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]
|
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
|
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
|
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
|
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.