Længste stigende delsekvens
O(n^2)-DP og derefter O(n log n)-tricket
Længste stigende delsekvens er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad er en LIS
En delsekvens bevarer rækkefølgen, men springer elementer over. Den længste stigende er den længste sådan sekvens, der er strengt stigende.
a = [3, 1, 4, 1, 5, 9, 2]Delsekvens, ikke delarray
I modsætning til et delarray behøver en LIS ikke være sammenhængende. Du kan springe mindre tal over for at holde kæden voksende.
DP-tilstanden i O(n^2)
Lad dp[i] være LIS-længden, der slutter ved indeks i. Ethvert element er i sig selv mindst en delsekvens af længde én.
dp = [1] * nOvergangen i O(n^2)
For hvert i ser du på alle tidligere j. Hvis a[j] er mindre, udvider 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)Aflæs svaret
Resultatet er den største værdi i tabellen, fordi LIS'en kan slutte hvor som helst, ikke kun ved det sidste indeks.
answer = max(dp)Hvorfor O(n²) kan give TLE
Den dobbelte løkke koster O(n²). Når n nærmer sig 100000, er det alt for langsomt og giver en afgørelse om overskredet tidsgrænse.
Idéen bag tålmodighedssortering
Den hurtigere metode holder en liste over den mindst mulige slutværdi for hver delsekvenslængde, ligesom ved tålmodighedssortering.
tails = []Brug bisect til at placere
For hvert tal laver du en binær søgning efter den rette plads blandt slutværdierne med bisect_left, hvilket giver O(n log n) i alt.
from bisect import bisect_leftUdvid eller erstat
Hvis pladsen ligger efter slutningen, bruger du append til at gøre LIS'en længere. Ellers overskriver du slutværdien med den mindre værdi.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLængden ligger i tails
Når gennemløbet er slut, er len(tails) LIS-længden. Listen i sig selv er ikke altid delsekvensen; kun dens længde er nøjagtig.
answer = len(tails)Strengt stigende kontra ikke-aftagende
For en ikke-aftagende variant skal du skifte til bisect_right, så ens værdier kan forlænge kæden.
from bisect import bisect_rightHurtigt tjek
Hvilken metode finder LIS-længden i O(n log n)?
Opsamling: Fra n² til n log n
Du kan nu løse LIS på to måder. DP-løsningen i O(n²) er enkel, mens metoden med slutværdier og bisect kan håndtere store inddata og holde sig inden for tidsgrænsen.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Længste stigende delsekvens” gratis?
Ja — hele teksten til “Længste stigende delsekvens” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Længste stigende delsekvens”?
O(n^2)-DP og derefter O(n log n)-tricket Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.
Hvor lang tid tager lektionen “Længste stigende delsekvens”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Memoization mod tabulation
- Definér tilstand og overgang
- Trappeklatring og møntkombinationer
- Længste stigende delsekvens