Vi har fått en matris med $n$ tal: $a$.Uppgiften är att hitta den längsta, strikt ökande, undersekvensen i $a$.

Formellt sett letar vi efter den längsta sekvensen av index $i_1, \dots i_k$ så att$$$i_1 < i_2 < \dots < i_k,\\a < a < \dots < a$$

I den här artikeln diskuterar vi flera algoritmer för att lösa den här uppgiften.Vi kommer också att diskutera några andra problem, som kan reduceras till detta problem.

Lösning på $O(n^2)$ med dynamisk programmering

Dynamisk programmering är en mycket allmän teknik som gör det möjligt att lösa en enorm klass av problem.Här tillämpar vi tekniken för vår specifika uppgift.

Först ska vi bara söka efter längden på den längsta ökande undersekvensen, och först senare lära oss hur man återställer själva undersekvensen.

Finnande av längden

För att lösa denna uppgift definierar vi en array $d$, där $d$ är längden på den längsta ökande undersekvensen som slutar i elementet vid index $i$.Vi kommer att beräkna denna array successivt: först $d$, sedan $d$ och så vidare. efter att denna array är beräknad kommer svaret på problemet att vara det maximala värdet i arrayen $d$.

Så låt det aktuella indexet vara $i$.D.v.s. vi vill beräkna värdet $d$ och alla tidigare värden $d, \dots, d$ är redan kända.Då finns det två alternativ:

• $d = 1$: den önskade undersekvensen består endast av elementet $a$.
• $d > 1$: då finns i den önskade undersekvensen ett annat tal före talet $a$.Låt oss fokusera på det talet:det kan vara vilket element som helst $a$ med $j = 0 \dots i-1$ och $a < a$.På detta sätt kan vi beräkna $d$ med hjälp av följande formel: Om vi fastställer indexet $j$, så har den längsta ökande undersekvensen som slutar med de två elementen $a$ och $a$ längden $d + 1$.Alla dessa värden $d$ är redan kända, så vi kan direkt beräkna $d$ med:$$d = \max_{\substack{j = 0 \dots i-1 \\ a < a}} \left(d + 1\right)$$

Om vi kombinerar dessa två fall får vi det slutliga svaret för $d$:

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

Implementation

Här är en implementering av den ovan beskrivna algoritmen som beräknar längden på den längsta ökande undersekvensen.

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;}

Restorera undersekvensen

Här har vi hittills bara lärt oss att hitta längden på undersekvensen, men inte hur man hittar själva undersekvensen.

För att kunna återskapa undersekvensen genererar vi ytterligare en hjälparray $p$ som vi kommer att beräkna tillsammans med arrayen $d$. $p$ kommer att vara index $j$ för det näst sista elementet i den längsta ökande undersekvensen som slutar med $i$. $p$ är med andra ord samma index $j$ vid vilket det högsta värdet $d$ erhölls.Denna hjälparray $p$ pekar i någon mening på förfäderna.

För att härleda underföljden börjar vi sedan bara vid indexet $i$ med det maximala $d$ och följer förfäderna tills vi har härlett hela underföljden, dvs. tills vi når elementet med $d = 1$.

Implementering av återställande

Vi kommer att ändra koden från de föregående avsnitten lite grann.Vi kommer att beräkna arrayen $p$ tillsammans med $d$, och därefter beräkna underföljden.

För enkelhetens skull tilldelar vi ursprungligen anfäderna med $p = -1$.För element med $d = 1$ kommer anfädernas värde att förbli $-1$, vilket kommer att vara något bekvämare för återställandet av underföljden.

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;}

Alternativt sätt att återställa underföljden

Det är också möjligt att återställa underföljden utan hjälparray $p$. vi kan helt enkelt räkna om det aktuella värdet på $d$ och även se hur maxvärdet uppnåddes.

Den här metoden leder till en något längre kod, men i gengäld sparar vi lite minne.

Lösning i $O(n \log n)$ med dynamisk programmering och binär sökning

För att få en snabbare lösning på problemet konstruerar vi en annan dynamisk programmeringslösning som löper på $O(n^2)$ och sedan senare förbättrar vi den till $O(n \log n)$.

Vi kommer att använda oss av den dynamiska programmeringsmatrisen $d$.Den här gången kommer $d$ att vara det element vid vilket en undersekvens av längden $i$ slutar.Om det finns flera sådana sekvenser tar vi den som slutar i det minsta elementet.

Initialt antar vi att $d = -\infty$ och för alla andra element $d = \infty$.

Vi kommer återigen att successivt bearbeta talen, först $a$, sedan $a$, osv. och i varje steg upprätthålla arrayen $d$ så att den är aktuell.

Efter att ha bearbetat alla element i $a$ är längden på den önskade undersekvensen den största $l$ med $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;}

Vi gör nu två viktiga observationer.

Arketen $d$ kommer alltid att vara sorterad: Och även elementet $a$ kommer bara att uppdatera högst ett värde $d$.

Därmed kan vi hitta detta element i matrisen $d$ med hjälp av binär sökning på $O(\log n)$.I själva verket letar vi helt enkelt i arrayen $d$ efter det första talet som är strikt större än $a$, och vi försöker uppdatera detta element på samma sätt som vid implementeringen ovan.

Implementering

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;}

Restorera underföljden

Det är också möjligt att återställa underföljden med denna metod.Den här gången måste vi upprätthålla två extra matriser. en som talar om index för elementen i $d$. och återigen måste vi skapa en matris med ”förfäder” $p$. $p$ kommer att vara indexet för det föregående elementet för den optimala undersekvensen som slutar i elementet $i$.

Det är lätt att upprätthålla dessa två matriser under iterationen över matrisen $a$ vid sidan av beräkningarna av $d$.Och i slutet är det inte svårt att återställa den önskade undersekvensen med hjälp av dessa matriser.

Lösning i $O(n \log n)$ med datastrukturer

Istället för ovanstående metod för att beräkna den längsta ökande undersekvensen i $O(n \log n)$ kan vi också lösa problemet på ett annat sätt: med hjälp av några enkla datastrukturer.

Låt oss gå tillbaka till den första metoden Kom ihåg att $d$ är värdet $d + 1$ med $j < i$ och $a < a$.

Om vi alltså definierar ytterligare en array $t$ så att$$$t] = d,$$då är problemet med att beräkna värdet $d$ likvärdigt med att hitta det maximala värdet i ett prefix av arrayen $t$:$$d = \max\left(t – 1] + 1\right)$$

Problemet med att hitta det maximala värdet i ett prefix av en array (som förändras) är ett standardproblem som kan lösas av många olika datastrukturer. Vi kan till exempel använda ett segmentträd eller ett Fenwick-träd.

Denna metod har uppenbarligen vissa brister: när det gäller längd och komplexitet i genomförandet kommer detta tillvägagångssätt att vara sämre än den metod som använder binär sökning.Om dessutom inmatningstalen $a$ är särskilt stora måste vi använda vissa knep, som att komprimera talen (dvs. numrera om dem från $0$ till $n-1$) eller använda ett implicit segmentträd (generera endast de grenar av trädet som är viktiga).Annars blir minnesförbrukningen för hög.

Å andra sidan har den här metoden också vissa fördelar: med den här metoden behöver man inte tänka på några knepiga egenskaper i den dynamiska programmeringslösningen.Och det här tillvägagångssättet gör det möjligt för oss att generalisera problemet mycket lätt (se nedan).

Relaterade uppgifter

Det finns flera problem som är nära besläktade med problemet med att hitta den längsta ökande undersekvensen.

Längsta icke minskande underföljd

Detta är faktiskt nästan samma problem.Bara att det nu är tillåtet att använda identiska tal i underföljden.

Lösningen är i huvudsak också nästan densamma.Vi behöver bara ändra olikhetstecknen och göra en liten ändring av den binära sökningen.

Antal längsta ökande undersekvenser

Vi kan använda den först diskuterade metoden, antingen $O(n^2)$-versionen eller den version som använder datastrukturer.Vi behöver bara dessutom lagra på hur många sätt vi kan få fram längsta ökande undersekvenser som slutar i värdena $d$.

Antalet sätt att bilda en längsta ökande undersekvens som slutar i $a$ är summan av alla sätt för alla längsta ökande undersekvenser som slutar i $j$ där $d$ är maximalt.Det kan finnas flera sådana $j$, så vi måste summera dem alla.

Med hjälp av ett segmentträd kan detta tillvägagångssätt också genomföras på $O(n \log n)$.

Det är inte möjligt att använda den binära sökmetoden för denna uppgift.

Minsta antal icke ökande undersekvenser som täcker en sekvens

För en given matris med $n$ siffror $a$ måste vi färglägga siffrorna i minsta möjliga antal färger, så att varje färg bildar en icke ökande undersekvens.

För att lösa detta märker vi att det minsta antalet nödvändiga färger är lika med längden på den längsta ökande underföljden.

Bevis: Vi måste bevisa dualiteten mellan dessa två problem.

Låt oss med $x$ beteckna längden på den längsta ökande undersekvensen och med $y$ det minsta antalet icke ökande undersekvenser som bildar en täckning.Vi måste bevisa att $x = y$.

Det är uppenbart att $y < x$ inte är möjligt, för om vi har $x$ strikt ökande element, så kan inte två av dem vara en del av samma icke ökande undersekvens.Därför har vi $y \ge x$.

Vi visar nu att $y > x$ inte är möjligt genom motsägelse.Anta att $y > x$.Då betraktar vi varje optimal uppsättning av $y$ icke ökande underföljder.Vi omvandlar denna mängd på följande sätt: så länge det finns två sådana undersekvenser så att den första börjar före den andra undersekvensen, och den första sekvensen börjar med ett tal som är större än eller lika med den andra, så kopplar vi bort detta starttal och fäster det vid början av den andra.Efter ett ändligt antal steg har vi $y$ undersekvenser, och deras startnummer kommer att bilda en ökande undersekvens av längden $y$.Eftersom vi antog att $y > x$ nådde vi en motsägelse.

Därmed följer att $y = x$.

Restorering av sekvenser: Den önskade uppdelningen av sekvensen i undersekvenser kan göras girigt, dvs. gå från vänster till höger och tilldela det aktuella numret eller den undersekvens som slutar med det minsta numret som är större än eller lika med det aktuella numret.

Praktikproblem

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