Najduži rastući podniz
Problem pronalaska najdužeg rastućeg podniza (engl. longest increasing subsequence) predstavlja algoritamski problem u kojem je potrebno odrediti najduži podniz ne obavezno uzastopnih elemenata datog niza, koji je rastući. Rešenje problema ne mora biti jedinstveno. Na primer, za niz {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, dužina najdužeg rastućeg podniza iznosi 6 i jedno od mogućih rešenja je podniz {0, 2, 6, 9, 13, 15}. Podnizovi {0, 4, 6, 9, 11, 15} i {0, 4, 6, 9, 13, 15} su takođe moguća rešenja datog problema. Problem pronalaska najdužeg rastućeg podniza se može rešiti u vremenu O(n log n), gde n označava dužinu ulaznog niza.
Veza sa drugim algoritamskim problemima uredi
Pronalazak najdužeg rastućeg podniza se može svesti na problem pronalaska najdužeg zajedničkog podniza, koji ima kvadratnu složenost. Najduži rastući podniz niza S je zapravo najduži zajednički podniz nizova S i T, gde je T sortiran niz S.
Rešenje zasnovano na dinamičkom programiranju uredi
Postoji pravolinijsko rešenje zasnovano na dinamičkom programiranju, koje, kao i rešenje zasnovano na problemu najdužeg zajedničkog podniza, ima kvadratnu složenost. Neka je sa D[k] označena dužina najdužeg rastućeg podniza niza A, sa ograničenjem da je poslednji element upravo A[k]. S obzirom da se globalno rešenje problema mora završiti u nekom elementu niza A, konačno rešenje problema se može dobiti pronalaskom maksimalne vrednosti u nizu D.
Za računanje elemenata niza D, može se primeniti sledeća rekurzivna formula. Za računanje vrednosti D[k], posmatramo skup svih indeksa Sk, za koje važi i < k i A[i] < A[k]. Ako je skup Sk prazan, tada su svi elementi koji se nalaze pre A[k] u nizu A veći od njega, pa je D[k] = 1. Inače, ako pronađemo maksimalnu dužinu najdužeg rastućeg podniza u okviru skupa Sk, tada samo dodamo element A[k] na kraj ovog niza. Dakle, važi sledeća formula:
Za rekonstrukciju jednog od rešenja, može se iskoristiti pomoćni niz P. Naime, P[k] će predstavljati indeks i, dobijen pri računanju D[k]. Najduži rastući podniz se može rekonstruisati jednim prolaskom kroz niz P od nazad.
Opis efikasnog rešenja uredi
Sledeći algoritam rešava efikasno problem pronalaska najdužeg rastućeg podniza uz upotrebu nizova i binarne pretrage. Algoritam redom obrađuje elemente ulaznog niza i u svakom trenutku računa najduži rastući podniz do tada obrađenih elemenata. Neka su elementi ulaznog niza označeni sa X[0], X[1], itd. Nakon obrade elementa X[i], čuvaju se sledeće vrednosti u dva niza:
- M[j] — čuva vrednost indeksa k niza X, takvu da je X[k] najmanji mogući poslednji element svih rastućih podnizova dužine j, gde je k ≤ i.
- P[k] — čuva indeks prethodnika od X[k] u najdužem rastućem podnizu koji se završava u X[k].
Dodatno, algoritam može čuvati u promenljivoj L dužinu do tada pronađenog najdužeg rastućeg podniza. Primetimo da, u bilo kom trenutku izvršavanja algoritma, niz
- X[M[1]], X[M[2]], ..., X[M[L]]
je neopadajući. Ukoliko postoji rastući podniz dužine i koji se završava u X[M[i]], onda postoji i podniz dužine i-1, koji se završava u manjoj vrednosti, tj. u vrednosti X[P[M[i]]]. Za pronalazak te vrednosti možemo iskoristiti binarnu pretragu koja ima logaritamsku složenost.
Pseudokod opisanog rešenja:
P = niz dužine N
M = niz dužine N + 1
L = 0
for i = 0 to N-1:
// Binarna pretraga najveceg broja j ≤ L
// takva da je X[M[j]] < X[i]
lo = 1
hi = L
while lo ≤ hi:
mid = ceil((lo+hi)/2)
if X[M[mid]] < X[i]:
lo = mid+1
else:
hi = mid-1
// Nakon pretrage, lo je za 1 veci od
// duzine najveceg prefiksa od X[i]
newL = lo
// Prethodnik od X[i] je poslednji indeks
// podniza duzine newL-1
P[i] = M[newL-1]
M[newL] = i
if newL > L:
// Ukoliko je pronadjen podniz duzine vece od bilo koje
// duzine koja je do sada pronadjena, azuriramo vrednost L
L = newL
// Rekonstruisemo najduzi rastuci podniz
S = array of length L
k = M[L]
for i = L-1 to 0:
S[i] = X[k]
k = P[k]
return S
S obzirom da algoritam koristi binarnu pretragu, složenost ovog rešenja iznosi O(n log n).
Implementacija u programskom jeziku C++ uredi
#define ARRAY_SIZE(A) sizeof(A)/sizeof(A[0])
// Binarna pretraga
int CeilIndex(int A[], int l, int r, int key) {
int m;
while( r - l > 1 ) {
m = l + (r - l)/2;
(A[m] >= key ? r : l) = m;
}
return r;
}
int LongestIncreasingSubsequenceLength(int A[], int size) {
int *tailTable = new int[size];
int len; // uvek pokazuje na praznu vrednost
tailTable[0] = A[0];
len = 1;
for( int i = 1; i < size; i++ ) {
if( A[i] < tailTable[0] )
// nova najmanja vrednost
tailTable[0] = A[i];
else if( A[i] > tailTable[len-1] )
// A[i] pokusava da prosiri najduzi podniz
tailTable[len++] = A[i];
else
// A[i] pokusava da postane kandidat za trenutni kraj postojeceg podniza
tailTable[CeilIndex(tailTable, -1, len-1, A[i])] = A[i];
}
delete[] tailTable;
return len;
}