Најдужи растући подниз

Проблем проналаска најдужег растућег подниза (енгл. 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], посматрамо скуп свих индекса S_k, за које важи i < k и A[i] < A[k]. Ако је скуп S_k празан, тада су сви елементи који се налазе пре A[k] у низу А већи од њега, па је D[k] = 1. Иначе, ако пронађемо максималну дужину најдужег растућег подниза у оквиру скупа S_k, тада само додамо елемент A[k] на крај овог низа. Дакле, важи следећа формула:

$D(k)=\max\{D(i)|\;i\ \in \ S_{k}\}\;+\;1$

За реконструкцију једног од решења, може се искористити помоћни низ 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;
}

Референце

• Увод у динамичко програмирање

Спољашње везе

• Имплементација алгоритма у програмском језику C++