Suurimman kasvavan osajonon löytämisen tehtävänä on löytää pisin kasvava osajono tietystä elementtijonosta.
Huomaa, että osasekvenssi ei välttämättä ole osamerkkijono (eli sen elementit eivät välttämättä ole peräkkäisiä alkuperäisessä sekvenssissä). Muodollisesti merkkijonolle x , jonka pituus on n , on tarpeen löytää maksimiluku l ja sitä vastaava kasvava indeksien sarja , jolloin . Suurimmalla kasvavalla osasekvenssillä on sovelluksia fysiikassa, matematiikassa, ryhmäesitysteoriassa, satunnaismatriisiteoriassa. Yleensä tämän ongelman ratkaisu tunnetaan ajassa n log n pahimmassa tapauksessa [1] .
Esitetään algoritmi ongelman ratkaisemiseksi, joka suoritetaan O( n log n ).
Merkkijonolle x tallennetaan taulukot M ja P , joiden pituus on n . M[i] sisältää tässä vaiheessa löydettyjen kasvavien osasekvenssien x n j , joiden pituus on i , , pienimmän viimeisistä alkioista . P[i] tallentaa edellisen merkin indeksin pisimmälle nousevalle osasekvenssille, joka päättyy i:nnen paikkaan. Jokaisessa vaiheessa tallennamme alisekvenssin nykyisen maksimipituuden ja viimeisen merkin vastaavan indeksin, muistaen säilyttää taulukoiden ominaisuudet. Vaihe on siirtymä merkkijonon seuraavaan elementtiin, jokainen siirtymä ei vaadi enempää kuin ajan logaritmi (binäärihaku taulukossa M ).
P = array of length N M = array of length N + 1 L = 0 for i in range 0 to N-1: 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 newL = lo P[i] = M[newL-1] M[newL] = i if newL > L: L = newL S = array of length L k = M[L] for i in range L-1 to 0: S[i] = X[k] k = P[k] return S
On selvää, että algoritmin suorittamisen jälkeen L on halutun osajonon pituus, ja itse elementit voidaan saada laajentamalla P rekursiivisesti indeksielementistä.