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

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

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 S_k, za koje važi i < k i A[i] < A[k]. Ako je skup S_k 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 S_k, tada samo dodamo element A[k] na kraj ovog niza. Dakle, važi sledeća formula:

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

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

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++

#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;
}

Reference

• Uvod u dinamičko programiranje

Spoljašnje veze

• Implementacija algoritma u programskom jeziku C++