Längsta växande delsekvens
O(n^2)-DP och därefter tricket i O(n log n)
Längsta växande delsekvens är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad LIS är
En delsekvens behåller ordningen men hoppar över element. Den längsta växande delsekvensen är den längsta sådana följd som ökar strikt.
a = [3, 1, 4, 1, 5, 9, 2]Delsekvens, inte subarray
Till skillnad från en subarray behöver en LIS inte vara sammanhängande. Du kan hoppa över mindre tal för att låta kedjan fortsätta växa.
DP-tillståndet för O(n^2)
Låt dp[i] vara längden på den LIS som slutar vid index i. Varje element är åtminstone en delsekvens med längden ett i sig själv.
dp = [1] * nÖvergången för O(n^2)
För varje i granskar du alla tidigare j. Om a[j] är mindre förlänger 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)Läs av svaret
Resultatet är det största värdet i tabellen, eftersom LIS kan sluta var som helst, inte bara vid det sista indexet.
answer = max(dp)Varför O(n^2) kan överskrida tidsgränsen
Den dubbla loopen kostar O(n i kvadrat). När n närmar sig 100000 är det alldeles för långsamt och ger ett tidsgränsbesked.
Idén bakom patience sorting
Den snabbare metoden lagrar en lista med det minsta möjliga slutvärdet för varje delsekvenslängd, ungefär som i patience sorting.
tails = []Använd bisect för att placera
För varje tal gör du en binärsökning efter rätt plats bland slutvärdena med bisect_left, vilket ger O(n log n) totalt.
from bisect import bisect_leftFörläng eller ersätt
Om platsen ligger efter slutet använder du append för att förlänga LIS. Annars skriver du över slutvärdet med det mindre värdet.
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xLängden finns i tails
När genomgången är klar är len(tails) LIS-längden. Listan själv är inte alltid delsekvensen; det är bara dess längd som är exakt.
answer = len(tails)Strikt växande kontra icke-avtagande
För en icke-avtagande variant byter du till bisect_right så att lika värden kan förlänga kedjan.
from bisect import bisect_rightSnabb kontroll
Vilken metod hittar LIS-längden i O(n log n)?
Sammanfattning: Från n^2 till n log n
Du kan nu lösa LIS på två sätt. DP-lösningen med O(n^2) är enkel, medan metoden med slutvärden och bisect fungerar för stora indata och klarar tidsgränsen.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Längsta växande delsekvens” gratis?
Ja – hela texten till ”Längsta växande delsekvens” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Längsta växande delsekvens”?
O(n^2)-DP och därefter tricket i O(n log n) Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Längsta växande delsekvens”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Memoisering kontra tabulering
- Definiera tillstånd och övergång
- Trappor och myntkombinationer
- Längsta växande delsekvens