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.
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.
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