# ADS úlohy E - podobne

Nejprve je potřeba si rozmyslet, zda přidání dalšího prvku na konec posloupnosti ovlivní dosavadní posloupnosti:

Budu-li postupovat v posloupnosti od konce do začátku, mohu najít první číslo, jehož rozdíl s posledním číslem přesáhne toleranci ($k$). Pro další výpočty pak mi stačí uvažovat pouze úsek napravo od tohoto čísla. Zároveň je však potřeba si uvědomit, že i předposlední číslo již vyhradilo jakýsi úsek, ve kterém má smysl zkoumat podposloupnosti - budu se tak zabývat kratším z těchto úseků.

Nyní vezmu následující situaci: mám posloupnost $P$ s finálním prvkem $P_{n+1}$, pro nějž je zarážka na pozici $s_1$.

Jelikož se jedná o první zarážku, celá posloupnost od $0$ do $n$ je platná a tuto posloupnost nelze rozšířit zleva ani zprava. Označím tak $t_0=n$ a $s_0=0$, což znamená, že podposloupnost má délku $t_0 - s_0$.

Dále, mezi $P_{s+1}$ a $P_{n+1}$ nevznikla žádná zarážka, a tak mohu postup opakovat (jako bych opět počítal od nuly), dokud nevznikne další zarážka.

## Algoritmus (1):

Vstup: posloupnost $P$ s prvky od $0$ do $n$, hranice $k$.

1. $s_0=0$
2. $x=0$
4. Pro $u \in \{1 \dots n\}$:
1. Pro $v \in \{u-1 \dots s_x\}:$
2. Je-li $|P_u-P_v|>k$:
1. $t_x=u$
2. $x=x+1$
3. $s_x=v+1$
5. Ukonči cyklus
5. $t_x=n$
6. Najdi takové $s_x$, aby rozdíl $t_x-s_x$ byl co největší.
7. Výstup: Nejdelší posloupnost prvků $P_{s_x} \dots P_{t_x-1}$.

## Zdůvodnění:

Algoritmus vlastně rozkouskuje interval na souvislé podposloupnosti, které již nejdou rozšířit. (nemusí být nutně disjunktní). Vybrat tu nejdelší nepředstavuje žádný problém.
Levá zarážka $s_x$ (inkluzivní) vzniká tehdy, kdy zkoumané číslo $P_u$ nelze odečíst od čísla před touto zarážkou - proto nelze posloupnost, ve které se nachází $P_u$, rozšířit směrem doleva. Ze stejného důvodu se $P_{u}$ stává pravou zarážkou (již nepatřící do ní) - $t_x$ pro předchozí podposloupnost.

## Složitost(1):

Pokud chci pouze nejdelší podposloupnost, pak mi stačí uchovávat si v paměti maximum a momentální podposloupnost, takže paměťové nároky budou konstantní. V opačném případě budu potřebovat lineární paměť na všechny zarážky.
Časová složitost závisí na tom, kolik budu mít zarážek. Nemám-li žádné, pak celá posloupnost je "v toleranci" a složitost tak bude kvadratická.

## Optimalizace:

Nevznikne-li pro daný prvek $P_u$ zarážka, pak pro následující prvky budu porovnávat rozdíl přes naprosto stejné prvky. Toto bych si mohl ušetřit tím, že pro daný interval zjistím maximum a minimum a budu porovnávat jen rozdíl mezi maximem a minimem.

## Algoritmus(2):

Vstup: posloupnost $P$ s prvky od $0$ do $n$, hranice $k$.

1. $s_0=0$
2. $x=0$
3. $maxim=- \infty, minim=+ \infty$
4. $d=0$
5. $z=true$
6. Pro $u \in \{1 \dots n\}$:
1. Je-li $z=false$ a je-li $|P_u-maxim|\leq k$ a $|P_u-minim|\leq k$:
2. $maxim=Max(P_u,maxim)$
3. $minim=Min(P_u,minim)$
4. Pokračuj dále
2. Jinak (je potřeba vytvořit zarážku):
3. $z=false$
4. Pro $v \in \{u-1 \dots s_x\}:$
5. Je-li $|P_u-P_v|>k$:
1. $z=true$
2. $t_x=u$
3. $x=x+1$
4. $s_x=v+1$
5. $maxim=Max(P_{s_x} \dots P_u)$
6. $minim = Min(P_{s_x} \dots P_u$
7. Ukonči cyklus
7. $t_x=n$
8. Najdi takové $s_x$, aby rozdíl $t_x-s_x$ byl co největší.
9. Výstup: Nejdelší posloupnost prvků $P_{s_x} \dots P_{t_x-1}$.

## Složitost (2):

Paměťová složitost výše popsaného je $O(n)$, pokud již zaznamenávám maximum, pak $O(1)$.

Co se týče časové složitosti: Pouhé rozšíření posloupnosti (nový prvek se vleze do tolerance maxima i minima) má složitost O(1). V případě, že je potřeba posloupnost uzavřít, může být opět potřeba prohledat $O(n)$ prvků, levá zarážka se posune o jeden prvek, a tak složitost v nejhorším případě by stále byla $O(n^2)$.