Решаем задачу нахождения длины наибольшей возрастающей подпоследовательности |
Содержание:
Последовательность Фибоначчи 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
| Комментировать | « Пред. запись — К дневнику — След. запись » | Страницы: [1] [Новые] |
