Saatetaan joukko, jossa on $n$ lukuja: $a$.Tehtävänä on löytää $a$:n pisin, tiukasti kasvava osajakso.

Formallisesti etsimme pisimmän indeksien $i_1, \pisteet i_k$ muodostaman sarjan, joka on sellainen, että$$$i_1 < i_2 < \pisteet < i_k,\\\a < a < \pisteet < a$$

Tässä artikkelissa käsittelemme useita algoritmeja, joilla voidaan ratkaista tämä tehtävä.Lisäksi käsittelemme joitain muitakin ongelmia, jotka voidaan pelkistää tähän ongelmaan.

Ratkaisu $O(n^2)$:ssa dynaamisella ohjelmoinnilla

Dynaaminen ohjelmointi on hyvin yleinen tekniikka, jonka avulla voidaan ratkaista valtava luokka ongelmia.Tässä sovellamme tekniikkaa tiettyyn tehtävään.

Aluksi etsimme vain pisimmän kasvavan osajakson pituuden, ja vasta myöhemmin opettelemme palauttamaan itse osajakson.

Pituuden löytäminen

Tehtävän suorittamiseksi määrittelemme matriisin $d$, jossa $d$ on sen pisimmän kasvavan osajakson pituus, joka päättyy elementtiin indeksillä $i$.Laskemme tämän matriisin vähitellen: ensin $d$, sitten $d$ ja niin edelleen.Kun tämä matriisi on laskettu, vastaus ongelmaan on matriisin $d$ suurin arvo.

Ole siis nykyinen indeksi $i$.Eli haluamme laskea arvon $d$ ja kaikki aiemmat arvot $d, \dots, d$ ovat jo tiedossa.silloin on kaksi vaihtoehtoa:

• $d = 1$: haluttu osajono koostuu vain elementistä $a$.
• $d > 1$: silloin vaaditussa osajonossa on toinen luku ennen lukua $a$. keskitytään tuohon lukuun: se voi olla mikä tahansa alkio $a$, jossa $j = 0 \dots i-1$ ja $a < a$.Näin voimme laskea $d$ seuraavan kaavan avulla:Jos kiinnitämme indeksin $j$, niin pisin kasvava osajono, joka päättyy kahteen alkioon $a$ ja $a$, on pituudeltaan $d + 1$.Kaikki nämä arvot $d$ ovat jo tiedossa, joten voimme suoraan laskea $d$ seuraavalla kaavalla:$$d = \max_{\substack{j = 0 \dots i-1 \\\ a < a}} \left(d + 1\right)$$$

Yhdistämällä nämä kaksi tapausta saamme lopullisen vastauksen $d$:

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

Toteutus

Tässä on edellä kuvatun algoritmin toteutus, joka laskee pisimmän kasvavan osajonon pituuden.

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

Taajuusjonon palauttaminen

Tähän mennessä opimme vain, miten löydämme osajonon pituuden, mutta emme sitä, miten löydämme itse osajonon.

Voidaksemme palauttaa osajonon generoimme ylimääräisen apumassan $p$, jonka laskemme massan $d$ rinnalla.$p$ on pisimmän kasvavan osajonon, joka päättyy arvoon $i$, toiseksi viimeisen alkion $j$ indeksi $j$.Toisin sanoen indeksi $p$ on sama indeksi $j$, jolla suurin arvo $d$ saatiin.Tämä apujoukko $p$ osoittaa tietyssä mielessä esivanhemmat.

Tällöin osajonon johtamiseksi aloitamme vain indeksistä $i$, jossa on suurin arvo $d$, ja seuraamme esivanhempia, kunnes olemme johtaneet koko osajonon, eli kunnes olemme saavuttaneet alkion, jonka arvo on $d = 1$.

Taannuttamisen toteuttaminen

Muutamme koodia edellisistä osioista hiukan.Laskemme matriisin $p$ rinnalle $d$, ja sen jälkeen laskemme osajonon.

Mukavuuden vuoksi annamme alun perin esivanhemmille arvoksi $p = -1$. Niille elementeille, joiden arvo on $d = 1$, esivanhempien arvo pysyy arvona $-1$, mikä on osajonon palauttamisen kannalta hieman kätevämpää.

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

Vaihtoehtoinen tapa palauttaa osajono

Voidaan myös palauttaa osajono ilman apumassamäärää $p$.Voimme yksinkertaisesti laskea uudelleen $d$:n nykyisen arvon ja katsoa myös, miten maksimi saavutettiin.

Tämä tapa johtaa hieman pidempään koodiin, mutta vastineeksi säästämme hieman muistia.

Ratkaisu $O(n \log n)$:ssä dynaamisella ohjelmoinnilla ja binäärihaulla

Saadaksemme nopeamman ratkaisun ongelmaan, konstruoimme erilaisen dynaamisen ohjelmoinnin ratkaisun, joka toimii $O(n^2)$:ssa, ja parannamme sitä myöhemmin $O(n \log n)$:ksi.

Käytämme dynaamisen ohjelmoinnin joukkoa $d$.Tällä kertaa $d$ on elementti, johon pituudeltaan $i$:n pituinen osajono päättyy.Jos tällaisia osajonoja on useita, otamme sen, joka päättyy pienimpään elementtiin.

Aluksi oletamme $d = -\infty$ ja kaikille muille elementeille $d = \infty$.

Käsittelemme taas asteittain lukuja, ensin $a$, sitten $a$ jne, ja jokaisessa vaiheessa ylläpidämme matriisia $d$ niin, että se on ajan tasalla.

Käsiteltyämme kaikki $a$:n alkiot halutun osajonon pituus on suurin $l$, jonka kohdalla $d on $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;}

Tehdään seuraavaksi kaksi tärkeätä havaintoa.

Matriisia $d$ lajitellaan aina lajiteltuna: Ja myös elementti $a$ päivittää vain korkeintaan yhden arvon $d$.

Siten voimme löytää tämän elementin matriisista $d$ käyttämällä binäärihakua $O(\log n)$:ssa.Itse asiassa etsimme yksinkertaisesti joukosta $d$ ensimmäistä lukua, joka on tiukasti suurempi kuin $a$, ja yritämme päivittää tämän alkion samalla tavalla kuin yllä olevassa toteutuksessa.

Toteutus

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

Tosasarjan palauttaminen

Tosasarjan palauttaminen on myös mahdollista tämän lähestymistavan avulla.Tällä kertaa meidän on ylläpidettävä kahta apumäärää.toinen, joka kertoo meille $d$:n elementtien indeksin.ja taas meidän on luotava ”esivanhempien” matriisi $p$.$p$ on elementtiin $i$ päättyvän optimaalisen osajonon edellisen elementin indeksi.

Näitä kahta matriisia on helppo ylläpitää matriisin $a$:n iteroinnin aikana matriisin $a$:n yli $d$:n laskentojen ohella.Ja lopussa ei ole vaikeaa palauttaa haluttua osajaksoa näiden matriisien avulla.

Ratkaisu $O(n \log n)$:ssä tietorakenteiden avulla

Ylläolevan menetelmän sijasta pisimmän kasvavan osajakson laskemiseksi $O(n \log n)$:ssä voimme ratkaista ongelman myös toisella tavalla: käyttämällä joitakin yksinkertaisia tietorakenteita.

Palataan ensimmäiseen menetelmään: Muistetaan, että $d$ on arvo $d + 1$, jossa $j < i$ ja $a < a$.

Jos siis määrittelemme lisämäärän $t$ siten, että $$$t] = d,$$,$$tällöin arvon $d$ laskemisen ongelma vastaa suurimman arvon etsimistä array $t$:n etuliitteestä: $$d = \max\vasen(t – 1] + 1\oikea)$$

Määrän etuliitteen suurimman arvon etsimisen ongelma arraysta (joka muuttuu) on vakio-ongelma, joka voidaan ratkaista monilla erilaisilla tietorakenteilla. Voimme esimerkiksi käyttää Segmenttipuuta tai Fenwick-puuta.

Tällä menetelmällä on ilmeisesti joitakin puutteita:pituuden ja toteutuksen monimutkaisuuden kannalta tämä lähestymistapa on huonompi kuin menetelmä, jossa käytetään binäärihakua.Lisäksi jos syöteluvut $a$ ovat erityisen suuria, meidän pitäisi käyttää joitakin temppuja, kuten lukujen pakkaamista (eli niiden uudelleenlukemista $0$:sta $n-1$:een) tai implisiittisen Segmenttipuun käyttämistä (generoimalla vain tärkeät oksat).Muuten muistin kulutus on liian suuri.

Toisaalta tällä menetelmällä on myös joitakin etuja:tällä menetelmällä ei tarvitse miettiä mitään hankalia ominaisuuksia dynaamisen ohjelmoinnin ratkaisussa.ja tämä lähestymistapa mahdollistaa ongelman yleistämisen hyvin helposti (ks. alla).

Seuraavat tehtävät

Tässä on useita ongelmia, jotka liittyvät läheisesti pisimmän kasvavan osajonon löytämisen ongelmaan.

Pisin ei-vähenevä osajono

Tämä on itse asiassa lähes sama ongelma.vain nyt osajonossa saa käyttää identtisiä lukuja.

Ratkaisu on periaatteessa myös lähes sama.Meidän täytyy vain muuttaa epätasa-arvon merkkejä ja tehdä pieni muutos binäärihakuun.

Pisimpien kasvavien osajaksojen lukumäärä

Voidaan käyttää ensin mainittua menetelmää, joko $O(n^2)$-versiota tai tietorakenteita käyttävää versiota.Meidän tarvitsee vain lisäksi tallentaa, kuinka monella tavalla saamme pisimpiä kasvavia osajaksoja, jotka päättyvät arvoihin $d$.

Tapojen lukumäärä muodostaa pisimpiä kasvavia osajaksoja, jotka päättyvät arvoon $a$, on kaikkien niiden tapojen summa, jotka koskevat kaikkia pisimpiä kasvavia osajaksoja, jotka päättyvät arvoon $j$ ja joiden kohdalla $d$ on suurin.Tällaisia $j$ voi olla useita, joten ne kaikki pitää laskea yhteen.

Segmenttipuuta käyttäen tämä lähestymistapa voidaan toteuttaa myös ajassa $O(n \log n)$.

Tehtävään ei voi käyttää binäärihakua.

Seurauksen peittävien ei-kasvavien osajaksojen pienin lukumäärä

Tietylle joukolle, jossa on $n$ lukuja $a$, meidän on väritettävä luvut pienimmällä määrällä värejä niin, että jokainen väri muodostaa ei-kasvavan osajakson.

Ratkaisemiseksi huomaamme, että tarvittavien värien pienin määrä on yhtä suuri kuin pisimmän kasvavan osajonon pituus.

Todistus: Meidän on todistettava näiden kahden ongelman kaksinaisuus.

Kirjoitetaan $x$:llä pisimmän kasvavan osajonon pituus ja $y$:llä pienin määrä ei-kasvavia osajonoja, jotka muodostavat peitteen.Meidän on todistettava, että $x = y$.

On selvää, että $y < x$ ei ole mahdollinen, koska jos meillä on $x$ tiukasti kasvavia alkioita, niin kaksi niistä ei voi kuulua samaan ei-kasvavaan osajonoon.Siksi meillä on $y \ge x$.

Osoitamme nyt, että $y > x$ ei ole mahdollinen ristiriidan kautta.Oletetaan, että $y > x$.Silloin tarkastellaan mitä tahansa optimaalista joukkoa $y$ ei-kasvavia osajaksoja.Muunnamme tämän joukon seuraavalla tavalla:niin kauan kuin on olemassa kaksi sellaista osajaksoa, joista ensimmäinen alkaa ennen toista osajaksoa, ja ensimmäinen osajakso alkaa luvulla, joka on suurempi tai yhtä suuri kuin toinen, niin irrotamme tämän aloitusluvun ja liitämme sen toisen osajakson alkuun.Lopullisen määrän vaiheiden jälkeen meillä on $y$ osajaksoja, ja niiden alkuluvut muodostavat kasvavan osajakson, jonka pituus on $y$.Koska oletimme, että $y > x$, päädyimme ristiriitaan.

Siten seuraa, että $y = x$.

Sekvenssien palauttaminen: Haluttu sekvenssin jako osajaksoihin voidaan tehdä ahneesti. ts. mennään vasemmalta oikealle ja annetaan nykyinen numero tai se osajakso, joka päättyy pienimpään numeroon, joka on suurempi tai yhtä suuri kuin nykyinen numero.

Harjoitustehtäviä

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