Chceme nájsť najdlhšiu súvislú podpostupnosť $a_l, \ldots, a_r$ (v skrátenom značení $[l,r]$), ktorej modus nie je unikátny – musia existovať aspoň dve čísla, ktoré sa v $[l,r]$ vyskytujú práve $f \ge k$ krát, a žiadne číslo sa v nej nesmie vyskytovať viac ako $f$-krát.

Najprv sa zamyslime nad tým, čo nám dáva veľké $k$. Existuje najviac $\lfloor n/k \rfloor$ rôznych čísel, ktoré sa môžu vyskytnúť $\ge k$ krát, lebo ak by ich bolo viac, postupnosť $a$ by musela mať $\ge (\lfloor n/k \rfloor + 1) k > n$ prvkov. Volajme ich časté. To nám pri hľadaní efektívneho algoritmu pomôže. Rovno si označme $c_{v,p}$ počet výskytov častého čísla $v$ medzi $a_1, \ldots, a_p$ (teda $c_{v,0} = 0$); tieto prefixové sumy môžeme predpočítať v čase aj pamäti $O(n^2/k)$.

Napr. $O(n^2)$ riešenie je zjavné – zoberieme si pevné $l$, začneme s $r = n$, postupne ho zmenšujeme a pamätáme si v poli, koľko čísel sa v $[l,r]$ vyskytuje práve $1,2,\ldots,n$ krát; vždy, keď zmenšíme $r$, sa zmenší počet výskytov jedného čísla, teda vieme ľahko aktualizovať tieto hodnoty a aktuálnu hodnotu $f$ (ktorá nemôže rásť), a nájdeme dokonca všetky podpostupnosti $[l,r]$ ktoré spĺňajú našu podmienku.

Pridajme teraz do tohto algoritmu podmienku, že sa zastavíme (a pokračujeme s ďalším $l$) hneď, keď nájdeme $r$ pre ktoré je modus neunikátny. Vtedy stačí skontrolovať, či sa modus vyskytuje aspoň $k$-krát a aktualizovať odpoveď na úlohu. Tu prichádza kľúčové pozorovanie:

• Označme $u$ najčastejšie číslo v $[l,n]$ (ak nie je jedinečné, potom niet čo riešiť).

• Pre každé $i \neq u$ nájdime maximálne $r$ také, že $c_{i,r}-c_{i,l-1} = c_{u,r}-c_{u,l-1}$, a označme ho $r_i$.

• Maximum všetkých $r_i$ je práve hľadané najväčšie $r$, pre ktoré má $[l,r]$ neunikátny modus.

Pointa je, že ak zoberieme maximálne $r_m$ a príslušné číslo $m$, potom čísla iné ako $u, m$ môžeme odignorovať, lebo žiadne z nich sa nevyskytuje v $[l,r_m]$ častejšie ako $u$. Dokážeme to sporom. Ak existuje $j \neq u,m$ také, že $(c_{u,r_m}-c_{u,l-1}) - (c_{j,r_m}-c_{j,l-1}) < 0$, ale $(c_{u,N}-c_{u,l-1}) - (c_{j,N}-c_{j,l-1}) > 0$, potom musí existovať nejaké $r > r_m$ také, že $c_{u,r}-c_{u,l-1} = c_{j,r}-c_{j,l-1}$. Ak totiž posúvame $r$ od $n$ po $r_m$ a sledujeme hodnotu výrazu $(c_{u,r}-c_{u,l-1}) - (c_{j,r}-c_{j,l-1})$, pri každom posunutí $r$ o $1$ sa výraz zmení maximálne o $1$, teda musíme medzi záporným a kladným číslom natrafiť na nulu. Potom by ale bolo $r_j \ge r$, teda väčšie ako $r_m$, čo je spor s maximálnosťou $r_m$.

Na prvý pohľad toto pozorovanie nevyzerá až tak užitočne, ale hovorí nám, že $u$ bude modus aj pre podpostupnosť $[l,r_m]$ a že hodnoty vo vstupnom poli sú dosť nezávislé – pre dané $l$ (a teda $u$) sa stačí pozrieť na všetky dvojice $(m,r)$, vybrať tie pre ktoré platí $c_{m,r}-c_{m,l-1} = c_{u,r}-c_{u,l-1}$, a z nich vybrať maximálne $r$. Prepíšme si túto rovnicu na $$c_{u,r}-c_{m,r} = c_{u,l-1}-c_{m,l-1} \,.$$

Pre každú dvojicu $(u,m)$ teda môžeme spraviť toto: zoskupíme všetky indexy $i$ podľa hodnoty $c_{u,i}-c_{m,i}$ v čase $O(n)$, pre každú hodnotu sa pozrieme na všetky jej indexy $i=l-1$, pre ktoré je $u$ modusom $[l,n]$, a vieme pre ne maximálny index $i=r$, ktorý dá rovnakú hodnotu. Takto pre každé $l$ spočítame maximálne $r$, pre ktoré má $[l,r]$ neunikátny modus, alebo zistíme, že žiadne také $r$ neexistuje. Nakoniec pre každý z týchto $O(n)$ kandidátov $[l,r]$ skontrolujeme, či sa modus $[l,n]$ (ktorý je aj modus $[l,r]$) vyskytuje v $[l,r]$ aspoň $k$ krát a spočítame odpoveď. To funguje v čase $O(n^3/k^2)$.

Ešte to môžeme zrýchliť. Samozrejme, možných trojíc $(u,m,i=l-1)$ je len $O(n^2/k)$, lebo $l$ jednoznačne určuje $u$. Pre $(u,m,i=r)$ zasa využime nápad s posúvaním $r$. Na začiatku ($r=n$) je $u$ unikátny modus a bude to tak až kým nenarazíme na $r=r_m$. Keďže posunutím $r$ o $1$ sa môže zmeniť len počet výskytov jedného čísla, pri posunutí z $r=r_m+1$ na $r=r_m$ musí to číslo byť $u$, teda chceme $a_{r+1} = u$. Vidíme, že celkovo stačí uvažovať len $O(n^2/k)$ trojíc $(u,m,i)$, a rovnaká je aj časová náročnosť. Pamäťová náročnosť je stále $O(n^2/k)$.

(Pre zaujímavosť: rozšíriť riešenie úlohy na ľubovoľné $k$ je pomerne ľahké. Pre pevné $f < \sqrt{n}$ sa posúvame po poli, pamätáme si pre každú hodnotu jej nasledujúcich $f+1$ výskytov a na základe najbližších z $f$-tých a $f+1$-vých výskytov určíme najväčšiu súvislú podpostupnosť s neunikátnym modusom. Pri posunutí o jeden prvok sa veľa nemení, takže z odpovede pre $k+1$ vieme vypočítať odpoveď pre $k$ v čase $O(n)$.)