Výpočet můžeme často zrychlit tím, že si vstupní data nejprve upravíme do vhodné podoby, případně si něco dalšího předpočítáme a teprve z těchto dat počítáme výstup. Celý výpočet tedy rozdělíme do dvou fází — předzpracování a vlastního výpočtu.

Úloha: (nejčastěji se vyskytující číslo) Dostanete pole obsahující $n$ celých čísel a máte vypsat číslo, které se v poli vyskytuje nejčastěji.

Řešení: Hloupé řešení si pro každý prvek pole spočítá, kolikrát se v poli vyskytuje (pro každý prvek projde celé pole), a vybere ten s největším počtem výskytů. Jeho časová složitost je $\OO(n^2)$.

Řešení: Určitě vás napadne nejjednodušší možné předzpracování a to je setřídění dat. Setřídit pole umíme v čase $\OO(n\log n)$. Potom bude k nalezení nejčastěji se vyskytujícího čísla stačit jen jeden průchod pole. Ten proběhne v čase $\OO(n)$. Celkem toto řešení zabere čas $\OO(n\log n)$.

Úloha: (největší jedničková podmatice) Matice $A$ velikosti $n \times m$ obsahuje nuly a jedničky. Podmatice je souvislý obdélníkový výřez z matice $A$ (určený levým horním a pravým dolním rohem). Jedničková podmatice je podmatice obsahující samé jedničky. Najděte největší jedničkovou podmatici matice $A$.

$$ A=
\begin{pmatrix}
1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 1 \\
\end{pmatrix}
$$

Na obrázku je matice $A$ velikosti $6\times 9$. Největší jedničková podmatice obsahuje $9$ jedniček a její levý horní roh leží na pozici $(3,4)$.1

Řešení: Nejjednodušší řešení vyzkouší všechny možné polohy levého horního i pravého dolního rohu a pro jimi určenou podmatici zkontroluje, jestli se skládá ze samých jedniček. Této kontrole budeme jednoduše říkat testování podmatice.

Všech možných poloh levého horního rohu je $mn$. Stejně tak i poloh pravého dolního rohu. Otestování, jestli se jimi určená podmatice skládá ze samých jedniček vyžaduje průchod celé podmatice a trvá v nejhorším případě čas $\OO(mn)$. Celkem je časová složitost tohoto řešení $\OO(m^3 n^3)$.

Řešení: Zamysleme se nad tím, co je na výše uvedeném řešení neefektivní. Často testujeme podmatice, které se překrývají. Testování průniku obou podmatic by stačilo dělat jen jednou. Chceme-li se vyhnout opakovanému testování některých podmatic, tak si vhodně předzpracujeme vstupní data. Ke každé jedničce si spočítáme, kolik jedniček leží v souvislé řadě pod ní. Tento počet k jedničce přičteme. Získané údaje si můžeme uložit přímo do matice $A$ (nepotřebujeme pomocnou datovou strukturu), protože nuly zůstanou tam, kde byly a místo jedniček budeme mít v matici uložena nenulová čísla.

$$
\mbox{Z matice }
A=
\begin{pmatrix}
1 & 0 & 1 & 1 \\
1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 \\
\end{pmatrix}
\mbox{dostaneme matici }
B=
\begin{pmatrix}
2 & 0 & 4 & 3 \\
1 & 2 & 3 & 4 \\
0 & 1 & 2 & 1 \\
1 & 0 & 1 & 0 \\
\end{pmatrix}
.
$$

Toto předzpracování nám zabere čas $\OO(mn)$. Stačí každým sloupcem projít jednou od zdola nahoru, nuly ponechat beze změny a ke každé jedničce přičíst hodnotu prvku ležícího pod ní.

Jak hledat největší jedničkovou podmatici? Opět vyzkoušíme všechny polohy levého horního rohu ($mn$ možností). Pro každý levý horní roh budeme zkoumat všechny možné polohy pravého horního rohu (až $m$ možností). Pravý horní roh leží ve stejném řádku jako levý horní roh a mezi oběma rohy nesmí ležet žádná nula, jinak podmatice nebude jedničková.

Když už budeme znát levý i pravý horní roh podmatice, jak zjistíme velikost největší podmatice s těmito rohy? K tomu využijeme předvýpočtu. Každé číslo v řádku mezi levým a pravým horním rohem určuje velikost souvislého úseku jedniček ležícího ve sloupci pod ním (včetně jeho pozice). Takže stačí vzít minimum z těchto čísel. Velikost největší jedničkové podmatice určené horními rohy bude součin tohoto minima a vzdálenosti mezi horními rohy.

Nyní shrneme, jak bude probíhat celý výpočet. Vyzkoušíme všechny možné pozice levého horního rohu. Pro každý levý horní roh stačí postupovat vpravo, dokud nenarazíme na nulu nebo na pravý okraj matice $A$. V průběhu postupu zkoušíme polohy pravého horního rohu a počítáme celkové minimum na základě předchozí hodnoty.

Vlastní hledání jedničkové podmatice bude trvat čas $mn\cdot \OO(m)=\OO(m^2 n)$. Dohromady s předzpracováním toto řešení vyžaduje čas $\OO(m^2 n)$.

Řešení: Předchozí řešení můžeme ještě zrychlit. Provedeme ještě jedno předzpracování a spočítáme si i počet jedniček ležících nad každou pozicí. Kromě matice $B=(b_{ij})_n^m$, kde $b_{ij}$ je délka souvislého úseku jedniček začínajícího na $ij$ a ležícího pod pozicí $ij$, si vytvoříme matici $C=(c_{ij})_n^m$, kde $c_{ij}$ je délka souvislého úseku jedniček začínajícího na $ij$ a ležícího nad pozicí $ij$. Obě předzpracování stihneme provést v čase $\OO(mn)$.

Klíčovým pojmem pro celé řešení je význačná pozice. Pozice $ij$ je význačná, pokud za prvé $a_{ij}=1$ a za druhé buď $a_{i,j-1}=0$ nebo $a_{i,j-1}$ leží mimo matici $A$. Jinými slovy na význačné pozici leží $1$ a vlevo vedle ní je buď $0$ a nebo je pozice $ij$ na levém okraji matice $A$.

Každá maximální jedničková podmatice nejde rozšířit o sloupec doleva, protože se vedle její levé hranice nachází $0$ a nebo už tam končí matice $A$. To ale neznamená nic jiného, než že levý sloupec každé maximální jedničkové podmatice obsahuje význačnou pozici.

Jak bude probíhat hledání největší jedničkové podmatice? Pro každou význačnou pozici prozkoumáme všechny jedničkové podmatice, které ji obsahují ve svém levém sloupci. Provedeme to následovně. Začneme ve význačné pozici $ij$. Postupně budeme procházet doprava, dokud nenarazíme na nulu nebo pravý okraj matice $A$. V každém kroku, tedy na pozici $ik$, $k\geq j$, zjistíme velikost největší jedničkové podmatice obsahující obě pozice $ij$, $ik$. To provedeme stejně jako v předchozím řešení. Najdeme $b=\min\{b_{i,j}, b_{i,j+1}, \dots, b_{i,k-1}, b_{i,k} \}$ a $c=\min\{c_{i,j}, c_{i,j+1}, \dots, c_{i,k-1}, c_{i,k} \}$. Velikost největší takové jedničkové podmatice bude $(b+c-1)\cdot (k-j+1)$. Všechny pozice, na které jsme při postupu vpravo z význačné pozice vstoupili, nemohou být význačné, protože vlevo vedle nich leží $1$.

Když si vše dáme dohromady, tak stačí matici $A$ procházet po řádcích zleva doprava. V každém kroku jsme v jednom ze $3$ stavů. Buď stojíme na nule, nebo na význačné pozici a nebo rozšiřujeme předchozí význačnou pozici doprava. V každém kroku děláme jen konstantně mnoho práce. Proto bude nalezení největší jedničkové podmatice trvat jen čas $\OO(mn) + \OO(mn)$. To je obdivuhodné zrychlení, ne?