Najdłuższy podciąg rosnący

Podciągi o zadanych własnościach - Algorytmy: zakres rozszerzony (Python)

Podciąg nie musi być spójny: wybieramy elementy w kolejności, pomijając inne. `length[i]` to długość najdłuższego podciągu rosnącego kończącego się na elemencie i. Liczymy ją z wcześniejszych wyników, więc to pierwszy przykład programowania dynamicznego (więcej w osobnym temacie).

data = [5, 2, 8, 6, 3, 6, 9, 7]
length = [1] * len(data)
for i in range(len(data)):
    for j in range(i):
        if data[j] < data[i] and length[j] + 1 > length[i]:
            length[i] = length[j] + 1
print(length)
print("najdłuższy podciąg rosnący:", max(length))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.