Najdłuższy rosnący podciąg
Programowanie dynamiczne O(n^2), a następnie sztuczka O(n log n)
Najdłuższy rosnący podciąg to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Czym jest LIS
Podciąg zachowuje kolejność elementów, ale pomija niektóre z nich. Najdłuższy rosnący podciąg to najdłuższy taki podciąg, którego wartości ściśle rosną.
a = [3, 1, 4, 1, 5, 9, 2]Podciąg, nie podtablica
W przeciwieństwie do podtablicy, LIS nie musi być spójny. Można przeskakiwać nad mniejszymi liczbami, aby łańcuch nadal rósł.
Stan DP O(n^2)
Niech dp[i] oznacza długość LIS, która kończy się na indeksie i. Każdy element sam w sobie tworzy podciąg o długości co najmniej jeden.
dp = [1] * nPrzejście O(n^2)
Dla każdego i należy sprawdzić każde wcześniejsze j. Jeśli a[j] jest mniejsze, podciąg można rozszerzyć: dp[i] = max(dp[i], dp[j] + 1).
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)Odczytaj wynik
Wynikiem jest największa wartość w tabeli, ponieważ LIS może kończyć się w dowolnym miejscu, a nie tylko na ostatnim indeksie.
answer = max(dp)Dlaczego O(n^2) może przekroczyć limit czasu
Podwójna pętla ma koszt O(n do kwadratu). Dla n bliskiego 100000 jest to zdecydowanie zbyt wolne i kończy się werdyktem przekroczenia limitu czasu.
Idea sortowania cierpliwości
Szybsza metoda przechowuje listę najmniejszego możliwego ostatniego elementu dla każdej długości podciągu, podobnie jak sortowanie cierpliwości.
tails = []Użyj bisect do umieszczania
Dla każdej liczby należy wyszukać binarnie jej miejsce wśród końcowych elementów za pomocą bisect_left, uzyskując łączną złożoność O(n log n).
from bisect import bisect_leftRozszerz albo zastąp
Jeśli pozycja znajduje się za końcem, należy użyć append, aby wydłużyć LIS. W przeciwnym razie trzeba zastąpić ten ostatni element mniejszą wartością.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xDługość jest w tails
Po zakończeniu przetwarzania len(tails) oznacza długość LIS. Sama lista nie zawsze jest tym podciągiem — dokładna jest tylko jej długość.
answer = len(tails)Ściśle rosnący a niemalejący
W wariancie niemalejącym należy użyć bisect_right, aby równe wartości mogły rozszerzać łańcuch.
from bisect import bisect_rightSzybkie sprawdzenie
Jaka metoda znajduje długość LIS w czasie O(n log n)?
Podsumowanie: od n^2 do n log n
Potrafią już Państwo rozwiązać LIS na dwa sposoby. Proste DP o złożoności O(n^2) działa dobrze dla małych danych, a metoda tails z bisect skaluje się do dużych danych i pozwala uniknąć przekroczenia limitu czasu.
Często zadawane pytania
Czy lekcja „Najdłuższy rosnący podciąg” jest bezpłatna?
Tak — pełny tekst „Najdłuższy rosnący podciąg” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Najdłuższy rosnący podciąg”?
Programowanie dynamiczne O(n^2), a następnie sztuczka O(n log n) Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Najdłuższy rosnący podciąg”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Memoizacja kontra tabulacja
- Definiowanie stanu i przejścia
- Wspinanie się po schodach i kombinacje monet
- Najdłuższy rosnący podciąg