Zdefiniuj tablicę pomocniczą D (o rozmiarze takim jak ciągu głównego) i przechowuj w niej informacje o największej długości podciągu rosnącego, jaki kończy się na każdym z elementów ciągu głównego.
Na każdym elemencie ciągu kończy się podciąg rosnący o długości przynajmniej równej 1 (bo zawiera przynajmniej ten element)
Jeżeli rosnący podciąg ma być spójny:
W pętli porównuj : jeśli A[i] > A[i-1] to zwiększ długość podciągu o 1 element, czyli D[i] = D[i-1]+1
w przeciwnym razie rozpocznij nowy podciąg rosnący, czyli D[i]=1
Wartownicy przechowują największą długość podciągu maxi oraz indeks ostatniego elementu k.
Ostatecznie podciąg zawiera kolejne elementy od A[k]-maxi+1 do A[k]
Jeżeli rosnący podciąg ma być niekoniecznie spójny:
Będzie potrzebna dodatkowa tablica P o rozmiarze n, jako informacja o wybranych elementach podciągu: P[i] będzie pamiętać indeks poprzednika i-go elementu.
Każdy element A[i] trzeba porównać ze wszystkimi poprzednimi elementami A[j], gdzie j=0…i-1
Jeśli A[i]>A[j], to sprawdź czy zwiększenie D[j]+1 jest opłacalne, tzn. czy jest większe od aktualnego D[i].
Jeśli tak, to zaakceptuj D[j]+1 jako nową wartość D[i] oraz zapamiętaj indeks j jako poprzednika elementu i.
Wartownik k przechowuje indeks ostatniego elementu podciągu.
Cały podciąg można wypisać zaczynając od elementu o indeksie końcowym k, następnie przejść do jego poprzednika P[k], następnie do poprzednika poprzednika i tak aż do elementu, którego poprzednik jest nieokreślony. Podciąg będzie wypisany w porządku odwrotnym, malejąco.
Aby wypisać podciąg w porządku rosnącym, można napisać prostą funkcję rekurencyjną, która sięgnie do poprzednika przed wyświetleniem wartość bieżącego elementu.