We krijgen een array met $n$ getallen: $a$.De opdracht is de langste, strikt stijgende, subsequentie in $a$ te vinden.

Vormelijk zoeken we de langste rij van de indexen $i_1, \dots i_k$ zodanig dat$i_1 < i_2 < \dots < i_k,\a < a < \dots < a$

In dit artikel bespreken we meerdere algoritmen om deze opgave op te lossen.Ook bespreken we enkele andere problemen, die tot dit probleem kunnen worden herleid.

Oplossing in $O(n^2)$ met dynamisch programmeren

Dynamisch programmeren is een zeer algemene techniek waarmee een enorme klasse van problemen kan worden opgelost.Hier passen we de techniek toe voor onze specifieke opgave.

Eerst zullen we alleen de lengte van de langste stijgende subsequentie zoeken, en pas later leren hoe we de subsequentie zelf kunnen herstellen.

De lengte vinden

Om deze taak te volbrengen, definiëren we een array $d$, waarin $d$ de lengte is van de langste stijgende subsequentie die eindigt in het element op index $i$.We zullen deze array geleidelijk berekenen: eerst $d$, dan $d$, enzovoort.Nadat deze array is berekend, zal het antwoord op het probleem de maximumwaarde in de array $d$ zijn.

Laat de huidige index dus $i$ zijn.D.w.z. we willen de waarde $d$ berekenen en alle voorgaande waarden $d, d$ zijn al bekend.Dan zijn er twee mogelijkheden:

• $d = 1$: de vereiste subsequentie bestaat alleen uit het element $a$.
• $d > 1$: dan zit er in de vereiste subsequentie nog een getal vóór het getal $a$.Laten we ons op dat getal concentreren:het kan elk element $a$ zijn met $j = 0 punten i-1$ en $a < a$.Op deze manier kunnen we $d$ berekenen met de volgende formule:Als we de index $j$ vastleggen, dan heeft de langste stijgende subsequentie eindigend in de twee elementen $a$ en $a$ de lengte $d + 1$.Al deze waarden $d$ zijn al bekend, dus kunnen we $d$ direct berekenen met:$$d = \max_{\substack{j = 0 \dots i-1 \ a < a}}

Als we deze twee gevallen combineren krijgen we het uiteindelijke antwoord voor $d$:

$$d = \max_{\substack{j = 0 \dots i-1 \ a < a}} \left(d + 1)\right)$$

Uitvoering

Hier volgt een uitvoering van het hierboven beschreven algoritme, dat de lengte van de langste stijgende subsequentie berekent.

int lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a) d = max(d, d + 1); } } int ans = d; for (int i = 1; i < n; i++) { ans = max(ans, d); } return ans;}

Herstellen van de subsequentie

Tot nu toe hebben we alleen geleerd hoe we de lengte van de subsequentie kunnen vinden, maar niet hoe we de subsequentie zelf kunnen vinden.

Om de subsequentie te kunnen herstellen, genereren we een bijkomende hulparray $p$ die we naast de array $d$ zullen berekenen.$p$ is de index $j$ van het op één na laatste element in de langste stijgende subsequentie eindigend op $i$.Met andere woorden de index $p$ is dezelfde index $j$ waarop de hoogste waarde $d$ werd verkregen.Deze hulparray $p$ wijst in zekere zin naar de voorouders.

Om dan de subsequentie af te leiden, beginnen we gewoon bij de index $i$ met de hoogste waarde $d$, en volgen de voorouders tot we de volledige subsequentie hebben afgeleid, d.w.z. tot we het element met $d = 1$ bereiken.

Uitvoering van het herstellen

We zullen de code uit de vorige secties een klein beetje veranderen.We zullen de array $p$ naast $d$ berekenen, en daarna de subsequentie berekenen.

Voor het gemak wijzen we oorspronkelijk de ancestors toe met $p = -1$.Voor elementen met $d = 1$ blijft de waarde van de ancestors $-1$, wat iets handiger is voor het herstellen van de subsequentie.

vector<int> lis(vector<int> const& a) { int n = a.size(); vector<int> d(n, 1), p(n, -1); for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (a < a && d < d + 1) { d = d + 1; p = j; } } } int ans = d, pos = 0; for (int i = 1; i < n; i++) { if (d > ans) { ans = d; pos = i; } } vector<int> subseq; while (pos != -1) { subseq.push_back(a); pos = p; } reverse(subseq.begin(), subseq.end()); return subseq;}

Alternatieve manier om de subsequentie te herstellen

Het is ook mogelijk om de subsequentie te herstellen zonder de hulparray $p$.We kunnen gewoon de huidige waarde van $d$ herberekenen en ook zien hoe het maximum werd bereikt.

Deze methode leidt tot een iets langere code, maar in ruil daarvoor besparen we wat geheugen.

Oplossing in $O(n \log n)$ met dynamisch programmeren en binair zoeken

Om een snellere oplossing voor het probleem te verkrijgen, construeren we een andere dynamische programmeeroplossing die in $O(n^2)$ loopt, en verbeteren die later tot $O(n \log n)$.

We zullen de dynamische programmeermatrix $d$ gebruiken.Deze keer is $d$ het element waarin een subsequentie van lengte $i$ eindigt.Als er meerdere van zulke sequenties zijn, dan nemen we de sequentie die in het kleinste element eindigt.

In eerste instantie nemen we aan $d = -infty$ en voor alle andere elementen $d = \infty$.

We zullen weer geleidelijk de getallen verwerken, eerst $a$, dan $a$, enzovoort, en in elke stap de array $d$ zo onderhouden dat hij actueel is.

Na verwerking van alle elementen van $a$ is de lengte van de gewenste subsequentie de grootste $l$ met $d < \infty$.

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { for (int j = 1; j <= n; j++) { if (d < a && a < d) d = a; } } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

We doen nu twee belangrijke vaststellingen.

De array $d$ zal altijd gesorteerd zijn: $d \le d$ voor alle $i = 1 \le n$.En ook het element $a$ zal maar hooguit één waarde $d$ bijwerken.

Dus kunnen we dit element in de array $d$ vinden met binair zoeken in $O(\log n)$.In feite zoeken we gewoon in de array $d$ naar het eerste getal dat strikt groter is dan $a$, en we proberen dit element op dezelfde manier te updaten als de bovenstaande implementatie.

Implementatie

int lis(vector<int> const& a) { int n = a.size(); const int INF = 1e9; vector<int> d(n+1, INF); d = -INF; for (int i = 0; i < n; i++) { int j = upper_bound(d.begin(), d.end(), a) - d.begin(); if (d < a && a < d) d = a; } int ans = 0; for (int i = 0; i <= n; i++) { if (d < INF) ans = i; } return ans;}

Herstellen van de subsequentie

Het is ook mogelijk om de subsequentie te herstellen met deze aanpak.Deze keer moeten we twee hulparrays bijhouden. Eén die ons de index van de elementen in $d$ vertelt. En opnieuw moeten we een array van “voorouders” $p$ maken. $p$ zal de index van het vorige element zijn voor de optimale subsequentie die eindigt in element $i$.

Het is gemakkelijk om deze twee arrays bij te houden in de loop van de iteratie over de array $a$ naast de berekeningen van $d$.En aan het eind is het niet moeilijk om met behulp van deze arrays de gewenste subsequentie te herstellen.

Oplossing in $O(n \log n)$ met datastructuren

In plaats van bovenstaande methode voor het berekenen van de langste stijgende subsequentie in $O(n \log n)$ kunnen we het probleem ook op een andere manier oplossen: met behulp van enkele eenvoudige datastructuren.

Laten we teruggaan naar de eerste methode.Onthoud dat $d$ de waarde $d + 1$ is met $j < i$ en $a < a$.

Dus als we een extra array $t$ definiëren zodat$$t] = d,$$ dan is het probleem van het berekenen van de waarde $d$ equivalent aan het vinden van de maximale waarde in een prefix van de array $t$:$$d = \maximaal-links(t – 1] + 1$rechts)$$

Het probleem van het vinden van het maximum van een prefix van een array (die verandert) is een standaardprobleem dat met veel verschillende datastructuren kan worden opgelost. We kunnen bijvoorbeeld een Segment tree of een Fenwick tree gebruiken.

Deze methode heeft uiteraard enkele tekortkomingen: in termen van lengte en complexiteit van de implementatie zal deze aanpak slechter zijn dan de methode met binair zoeken.Bovendien, als de ingevoerde getallen $a$ bijzonder groot zijn, dan zouden we enkele trucs moeten gebruiken, zoals het comprimeren van de getallen (d.w.z. ze hernummeren van $0$ naar $n-1$), of een impliciete Segment tree gebruiken (alleen de takken van de boom genereren die belangrijk zijn).Anders wordt het geheugenverbruik te hoog.

Aan de andere kant heeft deze methode ook enkele voordelen:met deze methode hoef je niet na te denken over lastige eigenschappen in de dynamische programmeeroplossing.En met deze aanpak kunnen we het probleem heel gemakkelijk veralgemenen (zie hieronder).

Gerelateerde opgaven

Hier zijn verschillende problemen die nauw verwant zijn aan het probleem van het vinden van de langste toenemende subsequentie.

Langste niet-afnemende subsequentie

Dit is in feite bijna hetzelfde probleem.Alleen is het nu toegestaan om identieke getallen in de subsequentie te gebruiken.

De oplossing is in wezen ook bijna hetzelfde.We moeten alleen de ongelijkheidstekens veranderen, en de binaire zoekmethode een beetje aanpassen.

Aantal langste stijgende subsequenties

We kunnen de eerst besproken methode gebruiken, ofwel de $O(n^2)$ versie, ofwel de versie die gebruik maakt van datastructuren.We hoeven alleen nog maar op te slaan op hoeveel manieren we langst toenemende subsequenties kunnen verkrijgen die eindigen op de waarden $d$.

Het aantal manieren om een langst toenemende subsequentie te vormen die eindigt op $a$ is de som van alle manieren voor alle langst toenemende subsequenties die eindigen op $j$ waarbij $d$ maximaal is.Er kunnen meerdere van zulke $j$ zijn, dus we moeten ze allemaal optellen.

Met behulp van een Segment tree kan deze aanpak ook worden geïmplementeerd in $O(n log n)$.

Het is niet mogelijk om de binaire zoekaanpak voor deze taak te gebruiken.

Kleinste aantal niet-oplopende subsequenties dat een rij omvat

Voor een gegeven matrix met $n$ getallen $a$ moeten we de getallen inkleuren in het kleinste aantal kleuren, zodanig dat elke kleur een niet-oplopende subsequentie vormt.

Om dit op te lossen, merken we op dat het minimum aantal vereiste kleuren gelijk is aan de lengte van de langste stijgende subsequentie.

Proof:We moeten de dualiteit van deze twee problemen bewijzen.

Laat ons met $x$ de lengte van de langste stijgende subsequentie aanduiden en met $y$ het kleinste aantal niet-klimmende subsequenties die een omslag vormen.We moeten bewijzen dat $x = y$.

Het is duidelijk dat $y < x$ niet mogelijk is, want als we $x$ strikt stijgende elementen hebben, dan kunnen er geen twee deel uitmaken van dezelfde niet-klimmende subsequentie.Daarom hebben we $y > x$.

We laten nu zien dat $y > x$ niet mogelijk is door tegenspraak.Stel dat $y > x$.Dan beschouwen we een willekeurige optimale verzameling van niet-vermeerderende subsequenties van $y$.We transformeren deze verzameling op de volgende manier:zolang er twee zulke subsequenties zijn zodanig dat de eerste begint voor de tweede subsequentie, en de eerste sequentie begint met een getal groter dan of gelijk aan de tweede, dan haken we dit startgetal af en hechten het aan het begin van de tweede.Na een eindig aantal stappen hebben we $y$ subsequenties, en hun startgetallen zullen een oplopende subsequentie van lengte $y$ vormen.Daar we veronderstelden dat $y > x$ hebben we een tegenspraak bereikt.

Daaruit volgt dat $y = x$.

Herstellen van de sequenties:De gewenste verdeling van de sequentie in subsequenties kan gretig gebeuren.Dat wil zeggen, ga van links naar rechts en wijs het huidige nummer toe of die subsequentie die eindigt op het minimale nummer dat groter is dan of gelijk is aan het huidige nummer.

PraktijkProblemen

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces – LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – “North-East”