Најдужи растући подниз
Проблем проналаска најдужег растућег подниза (енгл. longest increasing subsequence) представља алгоритамски проблем у којем је потребно одредити најдужи подниз не обавезно узастопних елемената датог низа, који је растући. Решење проблема не мора бити јединствено. На пример, за низ {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}, дужина најдужег растућег подниза износи 6 и једно од могућих решења је подниз {0, 2, 6, 9, 13, 15}. Поднизови {0, 4, 6, 9, 11, 15} и {0, 4, 6, 9, 13, 15} су такође могућа решења датог проблема. Проблем проналаска најдужег растућег подниза се може решити у времену О(n log n), где n означава дужину улазног низа.
Веза са другим алгоритамским проблемима
[уреди | уреди извор]Проналазак најдужег растућег подниза се може свести на проблем проналаска најдужег заједничког подниза, који има квадратну сложеност. Најдужи растући подниз низа S је заправо најдужи заједнички подниз низова S и T, где је T сортиран низ S.
Решење засновано на динамичком програмирању
[уреди | уреди извор]Постоји праволинијско решење засновано на динамичком програмирању, које, као и решење засновано на проблему најдужег заједничког подниза, има квадратну сложеност. Нека је са D[k] означена дужина најдужег растућег подниза низа A, са ограничењем да је последњи елемент управо A[k]. С обзиром да се глобално решење проблема мора завршити у неком елементу низа A, коначно решење проблема се може добити проналаском максималне вредности у низу D.
За рачунање елемената низа D, може се применити следећа рекурзивна формула. За рачунање вредности D[k], посматрамо скуп свих индекса Sk, за које важи i < k и A[i] < A[k]. Ако је скуп Sk празан, тада су сви елементи који се налазе пре A[k] у низу А већи од њега, па је D[k] = 1. Иначе, ако пронађемо максималну дужину најдужег растућег подниза у оквиру скупа Sk, тада само додамо елемент A[k] на крај овог низа. Дакле, важи следећа формула:
За реконструкцију једног од решења, може се искористити помоћни низ P. Наиме, P[k] ће представљати индекс i, добијен при рачунању D[k]. Најдужи растући подниз се може реконструисати једним проласком кроз низ P од назад.
Опис ефикасног решења
[уреди | уреди извор]Следећи алгоритам решава ефикасно проблем проналаска најдужег растућег подниза уз употребу низова и бинарне претраге. Алгоритам редом обрађује елементе улазног низа и у сваком тренутку рачуна најдужи растући подниз до тада обрађених елемената. Нека су елементи улазног низа означени са X[0], X[1], итд. Након обраде елемента X[i], чувају се следеће вредности у два низа:
- M[j] — чува вредност индекса k низа X, такву да је X[k] најмањи могући последњи елемент свих растућих поднизова дужине ј, где је k ≤ i.
- P[k] — чува индекс претходника од X[k] у најдужем растућем поднизу који се завршава у X[k].
Додатно, алгоритам може чувати у променљивој L дужину до тада пронађеног најдужег растућег подниза. Приметимо да, у било ком тренутку извршавања алгоритма, низ
- X[M[1]], X[M[2]], ..., X[M[L]]
је неопадајући. Уколико постоји растући подниз дужине i који се завршава у X[M[i]], онда постоји и подниз дужине i-1, који се завршава у мањој вредности, тј. у вредности X[P[M[i]]]. За проналазак те вредности можемо искористити бинарну претрагу која има логаритамску сложеност.
Псеудокод описаног решења:
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
С обзиром да алгоритам користи бинарну претрагу, сложеност овог решења износи O(n log n).
Имплементација у програмском језику C++
[уреди | уреди извор]#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;
}