Vi får et array med $n$ tal: $a$.Opgaven er at finde den længste, strengt stigende undersekvens i $a$.

Formelt set søger vi efter den længste sekvens af indeks $i_1, \dots i_k$ sådan at$$$i_1 < i_2 < \dots < i_k,\\a < a < \dots < a$$

I denne artikel diskuterer vi flere algoritmer til løsning af denne opgave. vi vil også diskutere nogle andre problemer, der kan reduceres til dette problem.

Løsning i $O(n^2)$ med dynamisk programmering

Dynamisk programmering er en meget generel teknik, der gør det muligt at løse en meget stor klasse af problemer.Her anvender vi teknikken til vores specifikke opgave.

Først vil vi kun søge efter længden af den længste stigende undersekvens, og først senere lære at genoprette selve undersekvensen.

Findelse af længden

For at løse denne opgave definerer vi et array $d$, hvor $d$ er længden af den længste stigende undersekvens, der ender i elementet ved indeks $i$.Vi vil beregne dette array gradvist: først $d$, så $d$, osv. efter at dette array er beregnet, vil svaret på problemet være den maksimale værdi i arrayet $d$.

Lad det aktuelle indeks være $i$.Dvs. vi ønsker at beregne værdien $d$, og alle tidligere værdier $d, \dots, d$ er allerede kendt.Så er der to muligheder:

• $d = 1$: den ønskede undersekvens består kun af elementet $a$.
• $d > 1$: så er der i den krævede undersekvens et andet tal før tallet $a$.Lad os fokusere på dette tal:det kan være et hvilket som helst element $a$ med $j = 0 \dots i-1$ og $a < a$.På denne måde kan vi beregne $d$ ved hjælp af følgende formel: Hvis vi fastlægger indekset $j$, så har den længste stigende undersekvens, der ender med de to elementer $a$ og $a$, længden $d + 1$.Alle disse værdier $d$ er allerede kendt, så vi kan direkte beregne $d$ med:$$d = \max_{\substack{j = 0 \dots i-1 \\ a < a}} \left(d + 1\right)$$$

Hvis vi kombinerer disse to tilfælde får vi det endelige svar for $d$:

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

Implementering

Her er en implementering af den ovenfor beskrevne algoritme, som beregner længden af den længste voksende undersekvens.

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

Gendannelse af undersekvensen

Så langt har vi kun lært, hvordan man finder længden af undersekvensen, men ikke hvordan man finder selve undersekvensen.

For at kunne genskabe undersekvensen genererer vi et ekstra hjælpearray $p$, som vi beregner sammen med arrayet $d$. $p$ bliver indekset $j$ for det næstsidste element i den længste stigende undersekvens, der ender med $i$. $p$ er med andre ord det samme indeks $j$, som den højeste værdi $d$ blev opnået ved.Dette hjælpematrix $p$ peger i en vis forstand på forfædrene.

For at udlede underfølgen starter vi så bare ved indekset $i$ med den maksimale $d$ og følger forfædrene, indtil vi har udledt hele underfølgen, dvs. indtil vi når frem til elementet med $d = 1$.

Implementering af gendannelse

Vi vil ændre koden fra de foregående afsnit en smule.Vi vil beregne arrayet $p$ sammen med $d$, og bagefter beregne undersekvensen.

For nemheds skyld tildeler vi oprindeligt forfædrene med $p = -1$.For elementer med $d = 1$ vil forfædreneværdien forblive $-1$, hvilket vil være lidt mere praktisk for gendannelsen af undersekvensen.

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

Alternativ måde at genskabe undersekvensen på

Det er også muligt at genskabe undersekvensen uden hjælpearrayet $p$. vi kan blot genberegne den aktuelle værdi af $d$ og også se, hvordan maksimum blev nået.

Denne metode fører til en lidt længere kode, men til gengæld sparer vi noget hukommelse.

Løsning i $O(n \log n)$ med dynamisk programmering og binær søgning

For at opnå en hurtigere løsning på problemet konstruerer vi en anden dynamisk programmeringsløsning, der kører i $O(n^2)$, og senere forbedrer vi den til $O(n \log n)$.

Vi vil bruge den dynamiske programmeringsmatrix $d$.Denne gang vil $d$ være det element, ved hvilket en undersekvens af længde $i$ slutter.Hvis der er flere sådanne sekvenser, tager vi den, der slutter ved det mindste element.

I første omgang antager vi $d = -\infty$ og for alle andre elementer $d = \infty$.

Vi vil igen gradvist behandle tallene, først $a$, så $a$ osv. og i hvert trin vedligeholde arrayet $d$, så det er opdateret.

Efter behandling af alle elementerne i $a$ er længden af den ønskede undersekvens den største $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 to vigtige iagttagelser.

Arrayet $d$ vil altid være sorteret: Og også elementet $a$ vil kun opdatere højst én værdi $d$.

Dermed kan vi finde dette element i arrayet $d$ ved hjælp af binær søgning på $O(\log n)$.I virkeligheden leder vi blot i arrayet $d$ efter det første tal, der er strengt større end $a$, og vi forsøger at opdatere dette element på samme måde som i ovenstående implementering.

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

Gendannelse af underfølgen

Det er også muligt at gendanne underfølgen ved hjælp af denne fremgangsmåde.Denne gang skal vi vedligeholde to hjælpearrays. et, der fortæller os indekset for elementerne i $d$. og igen skal vi oprette et array af “forfædre” $p$. $p$ vil være indekset for det foregående element for den optimale undersekvens, der slutter i element $i$.

Det er let at vedligeholde disse to arrays i løbet af iterationen over arrayet $a$ sideløbende med beregningerne af $d$.Og til sidst er det i ikke svært at genskabe den ønskede undersekvens ved hjælp af disse arrays.

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

I stedet for ovenstående metode til beregning af den længste voksende undersekvens i $O(n \log n)$ kan vi også løse problemet på en anden måde: ved hjælp af nogle simple datastrukturer.

Lad os gå tilbage til den første metode: Husk, at $d$ er værdien $d + 1$ med $j < i$ og $a < a$.

Så hvis vi definerer et ekstra array $t$ således, at $$$t] = d,$$så svarer problemet med at beregne værdien $d$ til at finde den maksimale værdi i et præfiks af arrayet $t$: $$d = \max\left(t – 1] + 1\right)$$

Problemet med at finde maksimum i et præfiks af et array (som ændrer sig) er et standardproblem, som kan løses af mange forskellige datastrukturer. Vi kan f.eks. bruge et segmenttræ eller et Fenwick-træ.

Denne metode har naturligvis nogle mangler: med hensyn til længde og kompleksitet af implementeringen vil denne fremgangsmåde være værre end metoden med binær søgning.Hvis indgangstallene $a$ er særligt store, vil vi desuden være nødt til at bruge nogle tricks, f.eks. komprimere tallene (dvs. omnummerere dem fra $0$ til $n-1$) eller bruge et implicit segmenttræ (kun generere de grene af træet, som er vigtige).Ellers vil hukommelsesforbruget blive for stort.

På den anden side har denne metode også nogle fordele: Med denne metode behøver man ikke at tænke på nogen vanskelige egenskaber i den dynamiske programmeringsløsning. og denne fremgangsmåde giver os mulighed for at generalisere problemet meget let (se nedenfor).

Relaterede opgaver

Her er flere problemer, der er nært beslægtede med problemet med at finde den længste voksende undersekvens.

Længste ikke-aftagende undersekvens

Dette er faktisk næsten det samme problem.Kun er det nu tilladt at bruge identiske tal i undersekvensen.

Løsningen er i det væsentlige også næsten den samme.Vi skal blot ændre ulighedstegnene og foretage en lille ændring af den binære søgning.

Antal længste stigende undersekvenser

Vi kan bruge den først omtalte metode, enten $O(n^2)$-versionen eller den version, der anvender datastrukturer.Vi skal blot yderligere gemme på hvor mange måder vi kan opnå længste voksende undersekvenser, der ender i værdierne $d$.

Antal måder at danne en længste voksende undersekvenser, der ender i $a$, er summen af alle måder for alle længste voksende undersekvenser, der ender i $j$, hvor $d$ er maksimalt.Der kan være flere sådanne $j$, så vi skal summere dem alle.

Ved hjælp af et segmenttræ kan denne fremgangsmåde også gennemføres på $O(n \log n)$.

Det er ikke muligt at bruge den binære søgemetode til denne opgave.

Mindste antal ikke-vækstende undersekvenser, der dækker en sekvens

For et givet array med $n$ tal $a$ skal vi farvelægge tallene i det mindste antal farver, således at hver farve danner en ikke-vækstende undersekvens

.

For at løse dette problem bemærker vi, at det mindste antal nødvendige farver er lig med længden af den længste stigende undersekvens.

Bevis: Vi skal bevise dualiteten af disse to problemer.

Lad os med $x$ betegne længden af den længste voksende delfølge og med $y$ det mindste antal ikke-vækstende delfølger, der danner et dække.Vi skal bevise, at $x = y$.

Det er klart, at $y < x$ ikke er muligt, for hvis vi har $x$ strengt voksende elementer, så kan ingen af dem være en del af den samme ikke-vækstende delfølge.Derfor har vi $y \ge x$.

Vi viser nu ved modsigelse, at $y > x$ ikke er muligt.Antag, at $y > x$.Så betragter vi et hvilket som helst optimalt sæt af $y$ ikke-vækstende delfølger.Vi omdanner denne i mængde på følgende måde: Så længe der findes to sådanne undersekvenser, således at den første begynder før den anden undersekvens, og den første sekvens begynder med et tal, der er større end eller lig med den anden, så hægter vi dette starttal af og knytter det til begyndelsen af den anden.Efter et endeligt antal trin har vi $y$ undersekvenser, og deres startnumre vil danne en stigende undersekvens af længde $y$.Da vi antog, at $y > x$, nåede vi frem til en modsigelse.

Deraf følger, at $y = x$.

Gentring af sekvenserne: Den ønskede opdeling af sekvensen i delsekvenser kan ske grådigt.Dvs. gå fra venstre mod højre og tildeler det aktuelle tal eller den delsekvens, der slutter med det mindste tal, som er større end eller lig med det aktuelle tal.

Praksisproblemer

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