Перейти к содержимому
Skein

наибольшая возрастающая подпоследовательность (LIS)

EN: longest increasing subsequence (LIS)

Самая длинная строго возрастающая подпоследовательность массива. Одномерное ДП решает задачу за O(n²), где dp[i] — длина лучшей подпоследовательности, заканчивающейся в i; бинарный поиск по массиву tails улучшает её до O(n log n).

хоткеиразвернуть
поиск
⌘K
пред. пьеса
k
след. пьеса
j
тиры
t
это меню
?