# Domácí úkol - úloha unikum

Hledám nejdelší posloupnost prvků těsně za sebou, aby se žádná hodnota neopakovala.

Může nastat hraniční případ, že posloupnost žádné prvky nemá, pak délku prohlásím za nulovou a jsem hotov.

Jinak si první prvek označím jako $a = 0$ a procházím posloupnost zleva doprava. Jakmile narazím na prvek, který je totožný s některým s předchozích prvků (označím $i,k; i<k$), provedu následující dva kroky:

- Ukončím posloupnost před prvkem k. Pak je délka takové podposloupnosti rovna $k-a$. Je-li tato délka větší než průběžné maximum (inicializované na $0$), můžu maximum nahradit douto délkou, a zapamatuji si také prvek $a$, kde tato podposloupnost začíná.

- Pokračuji dále; začáteční prvek podposloupnosti nastavím na $a = i+1$. Tím je opět každý prvek unikátní, jelikož podposloupnost již neobashuje prvek $i$, který je totožný s prvkem $k$.

Dojdu-li do konce posloupnosti, porovnám délku podposloupnosti od prvku $a$ do konce s průběžným maximem $maximum$. Větší hodnota je pak výslednou délkou.

Je výsledná podposloupnost správná? Určitě se ve výsledku žádný prvek neopakuje. A výslednou podposloupnost nejde rozšířit ani směrem doleva (první prvek by byl totožný s posledním) ani doprava (poslední prvek by byl totožný s prvním nebo bych došel na konec posloupnosti).

Složitost: Jelikož na každý prvek sáhnu právě jednou, toto procházení má složitost $\Theta(n)$. Problémem je, jak zjistit, že se nový prvek v podposloupnosti již nachází.

## Konstantní paměť:
V nejhorším případě je taková složitost $O(k)$ - pokud budu při sáhnutí na nový prvek jej srovnávat (rovno/nerovno, nikoli větší/menší) se všemi dosavadními (od $a$ do $k-1$), pak se v nejhorším případě prvek v posloupnosti nenachází, a budu tedy muset dojít až do konce. To znamená, že musím posloupnost procházet od nultého indexu do $k-1$, což pro n prvků dohromady znamená řádově $n^2$.

Algoritmus jako pseudokód:
https://pastebin.com/WffXPVjs
V Pythonu bych mohl využít dotaz "$in$", ale to je efektivnější jen díky tomu, jak funguje interpret a čísla v Pythonu
Paměťová náročnost: $\Theta (n)$ jako délka vstupu
Časová náročnost: $O(n^2)$

## Jiné (efektivnější) řešení

*Pokud použiju pro ukládání prvků nějakou datovou strukturu (kromě výchozího seznamu), pak časová náročnost bude* $O(n*($prohledání DS+přidání do DS$))$. Pro toto řešení bude nejlepší slovník.

xxxxxx
Možná jsem se nad úkolem zamyslel trochu víc, než bylo potřeba. Druhou možností by bylo zapojit binární vyhledávání; projíté prvky budu ukládat do pomocného seznamu jako dvojice $(hodnota,index)$.

Pro každý nový prvek v posloupnosti pak projdu pomocný seznam bin. vyhledáváním; bude-li se hodnota s určitým prvkem shodovat, pak zjistím index této hodnoty. Pokud je pak $index \geq a$, pak se již číslo v dané podposloupnosti nachází; pokud $index<a$, posloupnost byla na daném indexu oříznuta a číslo se tak ve zkoumané podposloupnosti nenachází. Tím mohu této hodnotě v pomocném seznamu přiřadit vyšší index a pokračovat dále ve čtení posloupnosti.

Problém je však v tom, jak zařadit novou hodnotu do pomocného seznamu pro binární vyhledávání (posouvání prvků apod.)
Proto jsem tento postup zavrhl, a volím spíše naivní přístup, kde projdu všechny prvky z momentální podposloupnosti. Nicméně pokud by zasazení do pomocného seznamu probíhalo v konstantním čase, pak by paměťová náročnost byla v závislosti na počtu unikátních hodnot v rozmezí $n+2$ a $3n$ (posloupnost+pomocné hodnoty+pomocné indexy) a časová náročnost $O(n$ $log$ $n)$.