Lengste økende delsekvens
O(n^2)-DP og deretter trikset med O(n log n)
Lengste økende delsekvens er en gratis leksjon i Competitive Programming Academy på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Competitive Programming Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva LIS er
En delsekvens beholder rekkefølgen, men kan hoppe over elementer. Den lengste økende delsekvensen er den lengste slike sekvensen som øker strengt.
a = [3, 1, 4, 1, 5, 9, 2]Delsekvens, ikke subarray
I motsetning til en subarray trenger ikke en LIS å være sammenhengende. Du kan hoppe over mindre tall for å holde kjeden voksende.
DP-tilstanden O(n^2)
La dp[i] være lengden på LIS-en som ender på indeks i. Hvert element er i det minste en delsekvens med lengde én alene.
dp = [1] * nOvergangen O(n^2)
For hver i ser du på alle tidligere j. Hvis a[j] er mindre, utvider du: 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)Les av svaret
Resultatet er den største verdien i tabellen, siden LIS-en kan ende hvor som helst, ikke bare på den siste indeksen.
answer = max(dp)Hvorfor O(n^2) kan gi TLE
Dobbeltløkken koster O(n i andre). Når n nærmer seg 100000, går det altfor sakte og gir en avgjørelse på grunn av tidsgrensen.
Ideen fra patience sorting
Den raskere metoden opprettholder en liste med den minste mulige halen for hver delsekvenslengde, omtrent som patience sorting.
tails = []Bruk bisect til å plassere
For hvert tall bruker du binærsøk for å finne riktig plass blant halene med bisect_left, noe som gir O(n log n) totalt.
from bisect import bisect_leftUtvid eller erstatt
Hvis plassen er etter slutten, bruker du append for å gjøre LIS-en lengre. Ellers overskriver du halen med den mindre verdien.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLengden ligger i tails
Når gjennomgangen er ferdig, er len(tails) lik LIS-lengden. Selve listen er ikke alltid delsekvensen; bare lengden er nøyaktig.
answer = len(tails)Strengt økende kontra ikke-avtagende
For en ikke-avtagende variant bytter du til bisect_right, slik at like verdier kan utvide kjeden.
from bisect import bisect_rightRask sjekk
Hvilken metode finner LIS-lengden i O(n log n)?
Oppsummering: Fra n^2 til n log n
Du kan nå løse LIS på to måter. DP med O(n^2) er enkelt, mens tails-og-bisect-metoden skalerer til store inndata og holder seg innenfor tidsgrensen.
Lær deg Python med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Lengste økende delsekvens» gratis?
Ja – hele teksten i «Lengste økende delsekvens» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Competitive Programming Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Competitive Programming Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Lengste økende delsekvens»?
O(n^2)-DP og deretter trikset med O(n log n) Du øver på Competitive Programming Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Competitive Programming Academy?
Ingen tidligere erfaring er nødvendig. Competitive Programming Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.
Hvor lang tid tar leksjonen «Lengste økende delsekvens»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Competitive Programming Academy-leksjonen?
Ja. Alle Competitive Programming Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Memoisering mot tabulering
- Definer tilstand og overgang
- Trappegang og myntkombinasjoner
- Lengste økende delsekvens