Најдужи растући подниз
Проблем проналаска најдужег растућег подниза (енгл. 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;
}