- Wordt gevuld
- Wordt gelezen
- Antwoord
Langste stijgende deelrij (LIS)
Hoeveel getallen kun je uit een rij kiezen, met behoud van hun volgorde, zodat elk getal groter is dan het vorige? De langste stijgende deelrij geeft het antwoord. Typ een rij en zie hoe dynamisch programmeren voor elke positie de langste reeks uitrekent die daar eindigt. Druk op Afspelen om de tabel te zien vullen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Typ een rij getallen. Voor elke positie bevat de tabel de lengte van de langste stijgende reeks waarden die daar eindigt, en de eerdere positie waarop die aansluit. Vink Gelijke waarden toestaan aan voor reeksen die nooit dalen. Aan het eind wordt de reeks teruggelezen vanaf de laatste waarde. Nieuw voorbeeld maakt een andere rij. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.
Hoe het werkt
- Typ een rij getallen, gescheiden door komma's of spaties. Vink Gelijke waarden toestaan aan voor reeksen die nooit dalen.
- Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen.
- Zie hoe elke positie met alle eerdere vergeleken wordt en hoe daarna de langste reeks in oranje wordt teruggelezen.
Zo werkt de tabel
De tabel heeft drie rijen: de waarden, de lengte van de langste stijgende deelrij die op elke positie eindigt, en de positie waarop die aansluit. Een waarde alleen is een reeks van lengte 1. Daarna wordt elke eerdere positie gecontroleerd: is de waarde daar kleiner, dan kan de reeks die daar eindigt met deze waarde worden verlengd, wat één meer geeft dan haar lengte. De langste verlenging wint, en haar positie komt in de derde rij.
De reeks teruglezen
De langste stijgende deelrij eindigt op de positie met de grootste lengte. Vanaf daar zegt de derde rij welke positie ervoor komt, en de derde rij van die positie zegt welke daar weer voor komt, tot een positie zonder voorganger. Op volgorde gelezen vormen die waarden het antwoord. Met Gelijke waarden toestaan aangevinkt mag een waarde ook op een gelijke waarde volgen; dat geeft de langste reeks die nooit daalt.
Veelgestelde vragen
Wat is het verschil tussen een deelrij en een subarray?
Een subarray is een blok naast elkaar liggende waarden. Een deelrij houdt de volgorde aan maar mag waarden overslaan, dus in 3, 10, 2, 1, 20 vormen de waarden 3, 10 en 20 een stijgende deelrij, ook al staan 2 en 1 ertussen.
Hoe snel is het LIS-algoritme?
De tabelmethode vergelijkt elk paar posities: n·(n − 1)/2 vergelijkingen voor n waarden. Patience sorting doet het in O(n log n): het onthoudt voor elke lengte de kleinste waarde die een reeks van die lengte afsluit, en plaatst elke nieuwe waarde met binair zoeken.
Is de langste stijgende deelrij uniek?
Niet altijd. In 1, 3, 2, 4 hebben zowel 1, 3, 4 als 1, 2, 4 lengte 3. De tabel geeft de lengte, en het teruglezen vindt er één van.
Waar wordt de langste stijgende deelrij gebruikt?
Bij het vergelijken van bestanden en genomen, waar sommige methoden eerst overeenkomende regels zoeken en dan een stijgende deelrij van hun posities nemen; bij planning en puzzels met het stapelen van dozen; en in de wiskunde, waar de lengte van de LIS van een willekeurige schudding een beroemd onderzoeksobject is.
Wordt er iets verstuurd?
Nee. Alles wordt in je browser berekend, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor