Adott egy $n$ számot tartalmazó tömb: $a$.A feladat az $a$ leghosszabb, szigorúan növekvő részsorozatának megtalálása.

Formálisan az $i_1, \dots i_k$ indexek leghosszabb olyan sorozatát keressük, hogy$$i_1 < i_2 < \dots < i_k,\\\a < a < \dots < a$$

A cikkben több algoritmust is tárgyalunk a feladat megoldására, valamint néhány más, erre a problémára visszavezethető problémát.

Megoldás $O(n^2)$-ban dinamikus programozással

A dinamikus programozás egy nagyon általános technika, amellyel problémák hatalmas osztályát lehet megoldani, itt a mi konkrét feladatunkra alkalmazzuk a technikát.

Először csak a leghosszabb növekvő részsorozat hosszát keressük, és csak később tanuljuk meg, hogyan lehet magát a részsorozatot visszaállítani.

A hossz megtalálása

A feladat megoldásához definiálunk egy $d$ tömböt, ahol $d$ annak a leghosszabb növekvő részsorozatnak a hossza, amely az $i$ indexű elemben végződik.Ezt a tömböt fokozatosan fogjuk kiszámítani: először $d$, majd $d$, és így tovább, és miután ezt a tömböt kiszámítottuk, a feladat válasza a $d$ tömb legnagyobb értéke lesz.

Az aktuális index legyen tehát $i$.Vagyis ki akarjuk számítani a $d$ értéket, és az összes korábbi $d, \dots, d$ érték már ismert.ekkor két lehetőség van:

• $d = 1$: a kívánt részsorozat csak az $a$ elemből áll.
• $d > 1$: ekkor a kívánt részsorozatban az $a$ szám előtt van még egy szám.Koncentráljunk erre a számra:ez lehet bármilyen $a$ elem, amelynek $j = 0 \dots i-1$ és $a < a$.Így a következő képlet segítségével kiszámíthatjuk $d$-t:Ha rögzítjük a $j$ indexet, akkor a leghosszabb növekvő részsorozat, amely a két $a$ és $a$ elemben végződik, $d + 1$ hosszúságú.Mindezek az értékek $d$ már ismertek, így közvetlenül kiszámíthatjuk $d$-t a következővel:$$d = \max_{\substack{j = 0 \dots i-1 \\\\ a < a}} \left(d + 1\right)$$

Ha ezt a két esetet kombináljuk, akkor megkapjuk a végső választ $d$-ra:

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

Implementáció

Itt a fent leírt algoritmus implementációja, amely kiszámítja a leghosszabb növekvő részsorozat hosszát.

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

A részsorozat visszaállítása

Az eddigiekben csak azt tanultuk meg, hogyan találjuk meg a részsorozat hosszát, de azt nem, hogyan találjuk meg magát a részsorozatot.

Hogy vissza tudjuk állítani a részsorozatot, létrehozunk egy további $p$ segédtömböt, amelyet a $d$ tömb mellett fogunk kiszámítani. $p$ a $i$-ben végződő leghosszabb növekvő részsorozat utolsó előtti elemének $j$ indexe lesz, vagyis az $p$ index ugyanaz az index $j$, amelynél a legnagyobb értéket $d$ kaptuk.Ez a $p$ segédtömb bizonyos értelemben az ősökre mutat.

Ezután a részsorozat levezetéséhez csak a legnagyobb $d$ értékkel rendelkező $i$ indexnél kezdjük, és addig követjük az ősöket, amíg a teljes részsorozatot le nem vezettük, vagyis amíg el nem érjük a $d = 1$ értékű elemet.

A visszaállítás megvalósítása

Az előző részek kódját egy kicsit megváltoztatjuk.A $d$ mellé kiszámítjuk a $p$ tömböt, és utána kiszámítjuk a részsorozatot.

A kényelem érdekében az ősökhöz eredetileg $p = -1$ értéket rendelünk. $d = 1$ elem esetén az ősök értéke $-1$ marad, ami a részsorozat visszaállítása szempontjából valamivel kényelmesebb lesz.

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

A részsorozat visszaállításának alternatív módja

A részsorozat visszaállítása a $p$ segédtömb nélkül is lehetséges, egyszerűen újraszámolhatjuk a $d$ aktuális értékét, és azt is láthatjuk, hogyan értük el a maximumot.

Ez a módszer kissé hosszabb kódhoz vezet, de cserébe némi memóriát takarítunk meg.

Megoldás $O(n \log n)$-ban dinamikus programozással és bináris kereséssel

A probléma gyorsabb megoldása érdekében konstruálunk egy másik dinamikus programozási megoldást, amely $O(n^2)$-ban fut, majd később továbbfejlesztjük $O(n \log n)$-ra.

A $d$ dinamikus programozási tömböt fogjuk használni.Ezúttal $d$ az az elem lesz, ahol egy $i$ hosszúságú részsorozat véget ér.Ha több ilyen sorozat van, akkor azt vesszük, amelyik a legkisebb elemben végződik.

Először feltételezzük, hogy $d = -\infty$, minden más elemre $d = \infty$.

Ismét fokozatosan fogjuk feldolgozni a számokat, először $a$, majd $a$, stb. és minden lépésben úgy tartjuk fenn a $d$ tömböt, hogy az naprakész legyen.

Az $a$ összes elemének feldolgozása után a kívánt részsorozat hossza a legnagyobb $l$, amelynek $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;}

Most két fontos megállapítást teszünk.

A $d$ tömb mindig rendezett lesz: És az $a$ elem is csak legfeljebb egy $d$ értéket fog frissíteni.

Ezért ezt az elemet a $d$ tömbben bináris kereséssel $O(\log n)$ alatt megtalálhatjuk.Valójában egyszerűen csak megkeressük a $d$ tömbben az első olyan számot, amely szigorúan nagyobb, mint $a$, és ezt az elemet próbáljuk frissíteni a fenti megvalósításhoz hasonlóan.

Elérés

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

A részsorozat visszaállítása

A részsorozat visszaállítása is lehetséges ezzel a megközelítéssel.Ezúttal két segédtömböt kell fenntartanunk.az egyik a $d$ elemeinek indexét mondja meg.és ismét létre kell hoznunk egy $p$ “ősök” tömböt.$p$ lesz a $i$ elemben végződő optimális részsorozat előző elemének indexe.

Az $a$ tömbön való iteráció során a $d$ számításai mellett könnyen fenntarthatjuk ezt a két tömböt.A végén pedig nem nehéz e tömbök segítségével visszaállítani a kívánt részfolyamatot.

Megoldás $O(n \log n)$-ban adatszerkezetekkel

A leghosszabb növekvő részfolyamat $O(n \log n)$-ban történő kiszámítására a fenti módszer helyett más módon is megoldhatjuk a feladatot: néhány egyszerű adatszerkezet segítségével.

Kanyarodjunk vissza az első módszerhez: Ne feledjük, hogy $d$ az $d + 1$ érték $j < i$ és $a < a$ értékkel.

Ha tehát definiálunk egy további $t$ tömböt úgy, hogy$$t] = d,$$akkor a $d$ érték kiszámításának problémája egyenértékű a $t$ tömb egyik előtagjának maximális értékének megtalálásával:$$d = \max\left(t – 1] + 1\right)$$

A tömb (változó) előtagjának maximális értékének megtalálása egy standard probléma, amelyet sokféle adatszerkezettel lehet megoldani. Használhatunk például egy szegmensfát vagy egy Fenwick-fát.

Ez a módszer nyilvánvalóan rendelkezik néhány hiányossággal:a hossz és a megvalósítás bonyolultsága szempontjából ez a megközelítés rosszabb lesz, mint a bináris keresést használó módszer.ráadásul ha a $a$ bemeneti számok különösen nagyok, akkor néhány trükköt kell alkalmaznunk, mint például a számok tömörítése (azaz átszámozás $0$-ról $n-1$-ra), vagy egy implicit szegmensfa használata (csak a fa fontos ágait generáljuk).Ellenkező esetben a memóriafogyasztás túl nagy lesz.

Másrészt ennek a módszernek is van néhány előnye:ezzel a módszerrel nem kell semmilyen trükkös tulajdonságra gondolnunk a dinamikus programozási megoldásban.és ez a megközelítés lehetővé teszi, hogy a problémát nagyon könnyen általánosíthassuk (lásd alább).

Hasonló feladatok

Az alábbiakban több olyan probléma is van, amely szorosan kapcsolódik a leghosszabb növekvő részfolyamat megtalálásának problémájához.

Hosszabb nem csökkenő részsorozat

Ez tulajdonképpen majdnem ugyanaz a probléma, csak most megengedett, hogy a részsorozatban azonos számokat használjunk.

A megoldás lényegében szintén majdnem ugyanaz.Csak az egyenlőtlenség előjeleit kell megváltoztatnunk, és a bináris keresést kissé módosítanunk.

A leghosszabb növekvő részsorozatok száma

Az elsőként tárgyalt módszert használhatjuk, akár az $O(n^2)$ változatot, akár az adatszerkezeteket használó változatot.Csak azt kell pluszban tárolnunk, hogy a $d$ értékekben végződő leghosszabb növekvő részsorozatokat hányféleképpen kaphatjuk meg.

Az $a$-ban végződő leghosszabb növekvő részsorozat kialakításának módjainak száma az összes olyan $j$-ban végződő leghosszabb növekvő részsorozat módjainak összege, ahol $d$ maximális.Több ilyen $j$ is lehet, tehát az összeset össze kell összegeznünk.

Egy szegmensfa használatával ez a megközelítés is megvalósítható $O(n \log n)$ alatt.

Ez a feladat nem megoldható a bináris kereséses megközelítéssel.

Egy sorozatot lefedő nem növekvő részfolyamatok legkisebb száma

Egy adott $n$ számokat tartalmazó $a$ tömb esetén a számokat a legkisebb számú színben kell színeznünk úgy, hogy minden szín egy nem növekvő részfolyamatot képezzen.

A megoldáshoz észrevesszük, hogy a szükséges színek minimális száma egyenlő a leghosszabb növekvő részsorozat hosszával.

Bizonyítás:Bizonyítanunk kell a két probléma kettősségét.

Jelöljük $x$-nek a leghosszabb növekvő részsorozat hosszát, $y$-nak pedig a legkisebb számú nem növekvő részsorozatot, amely fedést alkot.Be kell bizonyítanunk, hogy $x = y$.

Egyértelmű, hogy $y < x$ nem lehetséges, mert ha $x$ szigorúan növekvő elemeink vannak, akkor kettő nem lehet ugyanannak a nem növekvő részsorozatnak a része.Ezért van $y \ge x$.

Mutatjuk most, hogy $y > x$ ellentmondásosan nem lehetséges.Tegyük fel, hogy $y > x$.Ekkor tekintsük az $y$ nem növekvő részfolyamatok bármely optimális halmazát.Ezt a halmazban a következő módon alakítjuk át:amíg van két ilyen részsorozat úgy, hogy az első a második részsorozat előtt kezdődik, és az első sorozat a másodiknál nagyobb vagy azzal egyenlő számmal kezdődik, addig ezt a kezdőszámot kiakasztjuk és a második elejéhez csatoljuk.Véges számú lépés után $y$ részsorozatunk lesz, és ezek kezdőszámai $y$ hosszúságú növekvő részsorozatot fognak alkotni.Mivel feltételeztük, hogy $y > x$, ellentmondáshoz jutottunk.

Ebből következik, hogy $y = x$.

Sorozatok visszaállítása:A sorozat részsorozatokra történő kívánt felosztását mohón is elvégezhetjük, azaz balról jobbra haladva az aktuális számot vagy azt a részsorozatot rendeljük hozzá, amelyik azzal a minimális számmal végződik, amelyik nagyobb vagy egyenlő az aktuális számmal.

gyakorlati feladatok

• Topkódoló – EgészSorozat
• Topkódoló – AutóMarket
• Kódoló – Turista
• Kódoló – Turista
• Kódoló. LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – “North-East”