Fyllda celler
Jämförelser
Längsta hittills

  • Fylls
  • Läses
  • Svar

Mer om den längsta växande delföljden

Längsta växande delföljd (LIS)

Hur många tal i en lista kan du välja, i samma ordning, så att varje tal är större än det förra? Den längsta växande delföljden svarar på det. Skriv en lista och se dynamisk programmering räkna ut, för varje position, den längsta kedjan som slutar där. Tryck på Spela för att se tabellen fyllas i, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst. Skriv en lista med tal. För varje position innehåller tabellen längden på den längsta växande kedjan av värden som slutar där, och den tidigare position som kedjan fortsätter. Kryssa i Tillåt lika värden för kedjor som aldrig går nedåt. På slutet läses kedjan baklänges från sitt sista värde. Nytt exempel skapar en annan lista. När brädet är markerat stegar piltangenterna, mellanslag spelar och pausar, och Home och End hoppar till början och slutet.

Hur det fungerar

  1. Skriv en lista med tal, åtskilda med kommatecken eller mellanslag. Kryssa i Tillåt lika värden för kedjor som aldrig går nedåt.
  2. Tryck på Spela, eller använd Steg och Bakåt för att gå ett steg i taget. Dra i stegreglaget för att hoppa var som helst.
  3. Se varje position jämföras med alla tidigare, och se sedan den längsta kedjan läsas baklänges i orange.

Så fungerar tabellen

Tabellen har tre rader: värdena, längden på den längsta växande delföljden som slutar vid varje position, och den position den fortsätter. Ett värde ensamt är en kedja med längd 1. Sedan kontrolleras varje tidigare position: om dess värde är mindre kan kedjan som slutar där förlängas med det här värdet, vilket ger en längd som är ett större. Den längsta förlängningen vinner, och dess position hamnar i tredje raden.

Läs kedjan baklänges

Den längsta växande delföljden slutar vid positionen med störst längd. Därifrån säger tredje raden vilken position som kommer före, och tredje raden för den positionen säger vilken som kommer före den, ända tills en position saknar föregångare. Lästa i ordning är de värdena svaret. Med Tillåt lika värden ikryssat får ett värde också komma efter ett lika stort, vilket ger den längsta kedjan som aldrig går nedåt.

Ofta ställda frågor

Vad är skillnaden mellan en delföljd och en delarray?

En delarray är ett block av intilliggande värden. En delföljd behåller ordningen men får hoppa över värden, så i 3, 10, 2, 1, 20 bildar värdena 3, 10 och 20 en växande delföljd trots att 2 och 1 står mellan dem.

Hur snabb är LIS-algoritmen?

Tabellmetoden jämför varje par av positioner: n·(n − 1)/2 jämförelser för n värden. Patienssortering klarar det på O(n log n): den håller för varje längd reda på det minsta värde som avslutar en kedja med den längden, och placerar varje nytt värde med binärsökning.

Är den längsta växande delföljden unik?

Inte alltid. I 1, 3, 2, 4 har både 1, 3, 4 och 1, 2, 4 längd 3. Tabellen ger längden, och baklängesläsningen hittar en av dem.

Var används den längsta växande delföljden?

När man jämför filer och genom, där vissa metoder först hittar matchande rader och sedan tar en växande delföljd av deras positioner; i schemaläggning och pussel om att stapla lådor; och i matematiken, där längden på LIS för en slumpmässig blandning är ett berömt studieobjekt.

Skickas något någonstans?

Nej. Allt räknas ut i din webbläsare, och dina senaste inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Gå till Editor