Máme zadáno pole s $n$ čísly: $a$.Úkolem je najít nejdelší, striktně rostoucí posloupnost v $a$.

Formálně hledáme nejdelší posloupnost indexů $i_1, \dots i_k$ takovou, že$i_1 < i_2 < \dots < i_k,\\a < a < \dots < a$$

V tomto článku probereme několik algoritmů pro řešení této úlohy. také probereme některé další problémy, které lze na tento problém redukovat.

Řešení za $O(n^2)$ pomocí dynamického programování

Dynamické programování je velmi obecná technika, která umožňuje řešit obrovskou třídu problémů. zde tuto techniku použijeme pro naši konkrétní úlohu.

Nejprve budeme hledat pouze délku nejdelší rostoucí podřetězce a teprve později se naučíme obnovovat podřetězce samotné.

Zjištění délky

Pro splnění této úlohy definujeme pole $d$, kde $d$ je délka nejdelší rostoucí podřetězce, která končí prvkem na indexu $i$.Toto pole budeme počítat postupně: nejprve $d$, pak $d$ a tak dále. po výpočtu tohoto pole bude odpovědí na úlohu maximální hodnota v poli $d$.

Nechť je tedy aktuální index $i$.Tj. chceme vypočítat hodnotu $d$ a všechny předchozí hodnoty $d, \dots, d$ jsou již známy. pak jsou dvě možnosti:

• $d = 1$: požadovaná posloupnost se skládá pouze z prvku $a$.
• $d > 1$: pak je v požadované posloupnosti před číslem $a$ další číslo. zaměřme se na toto číslo:může to být libovolný prvek $a$ s $j = 0 \dots i-1$ a $a < a$.Tímto způsobem můžeme vypočítat $d$ pomocí následujícího vzorce:Pokud zafixujeme index $j$, pak nejdelší rostoucí posloupnost končící dvěma prvky $a$ a $a$ má délku $d + 1$.Všechny tyto hodnoty $d$ již známe, takže můžeme přímo vypočítat $d$ pomocí:$$d = \max_{\substack{j = 0 \dots i-1 \\ a < a}}. \left(d + 1\right)$$

Pokud tyto dva případy spojíme, dostaneme konečnou odpověď pro $d$:

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

Implementace

Tady je implementace výše popsaného algoritmu, který počítá délku nejdelší rostoucí podřetězce.

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

Obnovení podřetězce

Dosud jsme se naučili pouze zjistit délku podřetězce, ale ne to, jak najít podřetězec samotný.

Abychom mohli obnovit posloupnost, vytvoříme další pomocné pole $p$, které budeme počítat vedle pole $d$. $p$ bude index $j$ předposledního prvku v nejdelší rostoucí posloupnosti končící na $i$. jinými slovy index $p$ je stejný index $j$, na kterém byla získána nejvyšší hodnota $d$.Toto pomocné pole $p$ ukazuje v jistém smyslu na předky.

Pro odvození posloupnosti pak stačí začít na indexu $i$ s nejvyšší hodnotou $d$ a postupovat po předcích, dokud neodvodíme celou posloupnost, tj. dokud nedojdeme k prvku s hodnotou $d = 1$.

Provedení obnovy

Kód z předchozích částí trochu pozměníme.Vedle $d$ spočítáme i pole $p$ a poté spočítáme následnost.

Pro pohodlí jsme původně předkům přiřadili hodnotu $p = -1$, pro prvky s $d = 1$ zůstane hodnota předků $-1$, což bude pro obnovení následnosti o něco pohodlnější.

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

Alternativní způsob obnovy následné posloupnosti

Obnovu následné posloupnosti je možné provést i bez pomocného pole $p$. můžeme jednoduše přepočítat aktuální hodnotu $d$ a také zjistit, jak bylo dosaženo maxima.

Tento způsob vede k o něco delšímu kódu, ale na oplátku ušetříme trochu paměti.

Řešení za $O(n \log n)$ pomocí dynamického programování a binárního prohledávání

Abychom získali rychlejší řešení úlohy, zkonstruujeme jiné řešení dynamického programování, které proběhne za $O(n^2)$, a později ho vylepšíme na $O(n \log n)$.

Použijeme dynamické programování pole $d$.Tentokrát $d$ bude prvek, na kterém končí posloupnost délky $i$, a pokud je takových posloupností více, pak vezmeme tu, která končí nejmenším prvkem.

Na začátku budeme předpokládat $d = -\infty$ a pro všechny ostatní prvky $d = \infty$.

Znovu budeme postupně zpracovávat čísla, nejprve $a$, pak $a$ atd. a v každém kroku budeme udržovat pole $d$ tak, aby bylo aktuální.

Po zpracování všech prvků $a$ je délka požadované posloupnosti největší $l$ s $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;}

Provedeme nyní dvě důležitá pozorování.

Pole $d$ bude vždy setříděné: A také prvek $a$ bude aktualizovat nejvýše jednu hodnotu $d$.

Tento prvek můžeme v poli $d$ najít pomocí binárního vyhledávání za $O(\log n)$.Ve skutečnosti prostě hledáme v poli $d$ první číslo, které je striktně větší než $a$, a snažíme se tento prvek aktualizovat stejným způsobem jako při výše uvedené implementaci.

Implementace

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

Obnovení posloupnosti

Tímto přístupem je také možné obnovit posloupnost.Tentokrát musíme udržovat dvě pomocná pole. jedno, které nám říká index prvků v $d$, a opět musíme vytvořit pole „předků“ $p$. $p$ bude index předchozího prvku pro optimální posloupnost končící prvkem $i$.

Tato dvě pole je snadné udržovat v průběhu iterace nad polem $a$ souběžně s výpočty $d$.A na konci není obtížné pomocí těchto polí obnovit požadovanou posloupnost.

Řešení za $O(n \log n)$ pomocí datových struktur

Místo výše uvedeného způsobu výpočtu nejdelší rostoucí posloupnosti za $O(n \log n)$ můžeme problém řešit také jiným způsobem: pomocí některých jednoduchých datových struktur.

Vraťme se k první metodě: Připomeňme si, že $d$ je hodnota $d + 1$ s $j < i$ a $a < a$.

Definujeme-li tedy další pole $t$ tak, že $$t] = d,$$ pak problém výpočtu hodnoty $d$ je ekvivalentní nalezení maximální hodnoty v prefixu pole $t$:$$d = \max\left(t – 1] + 1\right)$$

Problém nalezení maxima prefixu pole (který se mění) je standardní problém, který lze řešit mnoha různými datovými strukturami. Můžeme například použít Segmentový strom nebo Fenwickův strom.

Tato metoda má samozřejmě některé nedostatky:z hlediska délky a složitosti implementace bude tento přístup horší než metoda využívající binární vyhledávání. navíc pokud jsou vstupní čísla $a$ obzvlášť velká, pak bychom museli použít některé triky, jako je komprese čísel (tj. přečíslovat je z $0$ na $n-1$) nebo použít implicitní Segmentový strom (generovat pouze ty větve stromu, které jsou důležité).Jinak by byla spotřeba paměti příliš vysoká.

Na druhou stranu má tato metoda i některé výhody:u této metody nemusíme myslet na žádné záludné vlastnosti v řešení dynamického programování a tento přístup nám umožňuje problém velmi snadno zobecnit (viz dále).

Související úlohy

Existuje několik problémů, které s problémem hledání nejdelší rostoucí posloupnosti úzce souvisejí.

Nejdelší neklesající posloupnost

Jedná se vlastně o téměř stejný problém, jen je nyní povoleno použít v posloupnosti stejná čísla.

Řešení je v podstatě také téměř stejné.Jen musíme změnit znaménka nerovností a mírně upravit binární hledání.

Počet nejdelších rostoucích podřetězců

Můžeme použít první diskutovanou metodu, a to buď verzi $O(n^2)$ nebo verzi využívající datové struktury.Musíme pouze dodatečně uložit, kolika způsoby můžeme získat nejdelší rostoucí posloupnosti končící hodnotami $d$.

Počet způsobů vytvoření nejdelší rostoucí posloupnosti končící $a$ je součet všech způsobů pro všechny nejdelší rostoucí posloupnosti končící $j$, kde $d$ je maximální.Takových $j$ může být více, takže musíme sečíst všechny.

Pomocí stromu segmentů lze tento přístup také realizovat za $O(n \log n)$.

Pro tuto úlohu nelze použít přístup binárního vyhledávání.

Nejmenší počet nerostoucích podřetězců pokrývajících posloupnost

Pro dané pole s $n$ čísly $a$ musíme čísla obarvit na nejmenší počet barev tak, aby každá barva tvořila nerostoucí podřetězec.

K řešení tohoto problému si všimneme, že minimální počet požadovaných barev je roven délce nejdelší rostoucí posloupnosti.

Důkaz: Musíme dokázat dualitu těchto dvou problémů.

Označme $x$ délku nejdelší rostoucí posloupnosti a $y$ nejmenší počet nerostoucích posloupností, které tvoří obálku. potřebujeme dokázat, že $x = y$.

Je jasné, že $y < x$ není možné, protože máme-li $x$ striktně rostoucích prvků, pak žádné dva nemohou být součástí stejné nerostoucí posloupnosti.Proto máme $y \ge x$.

Nyní ukážeme, že $y > x$ není možné, a to pomocí kontradikce: Předpokládejme, že $y > x$. Pak uvažujeme libovolnou optimální množinu $y$ nerostoucích posloupností.Tuto množinu transformujeme následujícím způsobem:pokud existují dvě takové posloupnosti, že první začíná před druhou posloupností a první posloupnost začíná číslem větším nebo rovným druhé, pak toto počáteční číslo odpojíme a připojíme k začátku druhé.Po konečném počtu kroků máme $y$ posloupností a jejich počáteční čísla budou tvořit rostoucí posloupnost délky $y$. Protože jsme předpokládali, že $y > x$, dospěli jsme k rozporu.

Z toho vyplývá, že $y = x$.

Obnovení posloupnosti: Požadované rozdělení posloupnosti na posloupnosti lze provést chamtivě, tj. postupovat zleva doprava a přiřadit aktuální číslo nebo tu posloupnost končící minimálním číslem, které je větší nebo rovno aktuálnímu.

Praktické úlohy

• Topcoder – IntegerSequence
• Topcoder – AutoMarket
• Codeforces – Tourist
• Codeforces -. LCIS
• SPOJ – SUPPER
• Topcoder – BridgeArrangement
• ACMSGURU – „Severovýchod“