**Содержание:**

[Последовательность Фибоначчи O (n)][1]
[Решение за O(n ^ 2)][2]
[Бинарный поиск O(log n)][3]
[Решение за O(n \* log n)][4]



## Задача {#zadacha}



_"Найти длину самой большой возрастающей подпоследовательности в массиве."_



Вообще, это частный случай задачи нахождения общих элементов 2-х последовательностей, где второй последовательностью является та же самая последовательность, только отсортированная.



## На пальцах {#na-palcah}



Есть последовательность:



5, 10, 6, 12, 3, 24, 7, 8



Вот примеры подпоследовательностей:



10, 3, 8
5, 6, 3



А вот примеры возрастающих подпоследовательностей:



5, 6, 7, 8
3, 7, 8



А вот примеры возрастающих подпоследовательностей наибольшей длины:



5, 6, 12, 24
5, 6, 7, 8

[Читать дальше →][5]

[1]: #feb
[2]: #On
[3]: #Bin
[4]: #ONLogN
[5]: https://habrahabr.ru/post/343210/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut