Langste stijgende deelrij (LIS)

Kies getallen uit een rij, van links naar rechts, elk groter dan het vorige. Hoe lang kan zo'n keten worden? De vraag is eenvoudig genoeg voor een puzzelboek, en het antwoord verbindt een kaartspel, een klassieke tabel van dynamisch programmeren en een van de mooiste resultaten over willekeurige schuddingen.

Een rij staven van verschillende hoogte, waarvan een stijgende keten van links naar rechts in oranje is gemarkeerd
Een rij staven van verschillende hoogte, waarvan een stijgende keten van links naar rechts in oranje is gemarkeerd

Het probleem

Gegeven een rij getallen houdt een deelrij er een aantal van in hun oorspronkelijke volgorde. Ze is stijgend als elke waarde groter is dan de vorige. De langste stijgende deelrij, of LIS, is de langste zo'n keuze. Een rij van n waarden heeft 2ⁿ deelrijen, dus ze allemaal controleren werkt alleen voor heel korte rijen.

De tabel

Laat len[i] de lengte zijn van de langste stijgende deelrij die precies op positie i eindigt. Die is 1 voor de waarde alleen, of 1 + len[j] voor een eerdere positie j met een kleinere waarde, welke het grootst is. Elke positie kijkt terug naar alle eerdere, dus de tabel heeft n·(n − 1)/2 vergelijkingen nodig. Het antwoord is de grootste len[i], en als je noteert welke j elke len[i] opleverde, kun je de deelrij teruglezen.

Een voorbeeld

Neem 3, 10, 2, 1, 20, 4, 6, 7, 5, 9. Positie voor positie zijn de lengtes 1, 2, 1, 1, 3, 2, 3, 4, 3 en 5: de 20 verlengt 3, 10; de 4 verlengt de 3; de 6 verlengt de 4, de 7 de 6 en de 9 de 7. Teruglezen vanaf de 9 geeft 3, 4, 6, 7, 9, een stijgende deelrij van lengte 5.

Sneller: patience sorting

Deel de waarden als kaarten uit op stapels: elke waarde gaat op de meest linkse stapel waarvan de bovenste kaart niet kleiner is, of begint rechts een nieuwe stapel. Het aantal stapels is de lengte van de LIS. Omdat de bovenste kaarten van de stapels altijd gesorteerd zijn, is de juiste stapel met binair zoeken te vinden, zodat de hele methode O(n log n) stappen kost. Ze is genoemd naar het kaartspel patience, waar ze op lijkt.

Wat wiskunde

In 1935 bewezen Paul Erdős en George Szekeres dat elke rij van n² + 1 verschillende getallen een stijgende of een dalende deelrij van lengte n + 1 heeft. Stanislaw Ulam vroeg in 1961 hoe lang de LIS van een willekeurige schudding van n getallen is. Het antwoord, ongeveer 2√n voor grote n, werd in 1977 gevonden door Anatoly Vershik en Sergei Kerov en door Ben Logan en Larry Shepp, en in 1999 vonden Jinho Baik, Percy Deift en Kurt Johansson de precieze vorm van de schommelingen: de Tracy–Widom-verdeling uit de theorie van toevalsmatrices.

Paul Erdős tijdens een studentenseminar in Boedapest in 1992. In 1935 bewezen hij en George Szekeres dat elke lijst van n² + 1 verschillende getallen een stijgende of dalende deelrij van lengte n + 1 heeft.
Paul Erdős tijdens een studentenseminar in Boedapest in 1992. In 1935 bewezen hij en George Szekeres dat elke lijst van n² + 1 verschillende getallen een stijgende of dalende deelrij van lengte n + 1 heeft.
Portret van Stanisław Ulam
Portret van Stanisław Ulam

Probeer het zelf

Open de app en druk op Stap. De oranje kolom is de positie die wordt uitgerekend en de blauwe kolom de eerdere positie waarmee ze wordt vergeleken. De rij Lengte groeit als er langere reeksen worden gevonden, de rij Komt na onthoudt waar ze vandaan komen, en aan het eind wordt het antwoord in oranje teruggelezen en onder de tabel getoond.

Veelgestelde vragen

Wat is de tijdcomplexiteit van de LIS?

O(n²) met de tabel, omdat elke positie naar alle eerdere kijkt, en O(n log n) met patience sorting en binair zoeken. Beide hebben O(n) geheugen nodig.

Hoe vind ik de langste niet-dalende deelrij?

Laat een waarde ook op een gelijke waarde volgen: vergelijk met ≤ in plaats van <. Vink in de app Gelijke waarden toestaan aan. Leg bij patience sorting elke waarde op de meest linkse stapel waarvan de bovenste kaart strikt groter is.

Wat is de langste dalende deelrij?

Hetzelfde probleem met de vergelijking omgedraaid, of de LIS van de rij waarin elke waarde van teken is gewisseld. Volgens de stelling van Erdős–Szekeres heeft een lang genoeg rij altijd een lange stijgende of een lange dalende deelrij.

Hoe lang is de LIS van een willekeurige rij?

Voor een willekeurige schudding van n verschillende getallen ongeveer 2√n voor grote n. De correctie groeit als de zesdemachtswortel van n, dus voor duizend getallen is het gemiddelde ongeveer 58, iets minder dan 2√1000 ≈ 63.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Probeer de langste stijgende deelrij