Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности

Автор: PavelKatunin
Источник: https://habrahabr.ru/post/343210/

Содержание:

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


Задача


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


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


На пальцах


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


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

Читать дальше →
habrahabr
4
0 GOLOS
0
В избранное
habreplicator
На Golos с 2017 M04
4
0

Зарегистрируйтесь, чтобы проголосовать за пост или написать комментарий

Авторы получают вознаграждение, когда пользователи голосуют за их посты. Голосующие читатели также получают вознаграждение за свои голоса.

Зарегистрироваться
Комментарии (0)
Сортировать по:
Сначала старые