Динамическое программирование. Задача о возрастающей подпоследовательности наибольшей длины.

Условие

Задача о возрастающей подпоследовательности наибольшей длины: Дана последовательность чисел, необходимо найти наибольшую по длине возрастающую подпоследовательность.

Для последовательности {1, 4, 2, 5, 3} решение будет таким:

• f5 = 1 + max(f1, f3)
• f4 = 1 + max(f1, f2, f3)
• f3 = 1 + max(f1)
• f2 = 1 + max(f1)
• f1 = 1. Возвращаемся назад
• f2 = 1 + max(f1) = 2
• f3 = 1 + max(f1) = 2
• f4 = 1 + max(f1, f2, f3) = 3
• f5 = 1 + max(f1, f3) = 3. Решение есть max(f1, f2, f3, f4, f5) = 3.

Чтобы повторно не решать решённые подзадачи, введём массив c размером, хранящий значения вычисленных функций. Начальные значения его равны нулю — значению, которое не может быть верным решением любой из одзадач. Это позволит нам определить, решали ли мы эту подзадачу или нет. Если нет — запускаем решение для требуемого аргумента, и после получения результата сохраняем его.

Решение

Алгоритм сложностью O(n^2):

есть входной массив последовательности a[....], и массив dp[...], где будем хранить максимальное значение длины последовательности, так что dp[ i ] - это максимальная длина последовательности которая оканчивается на a[i].

Начальное значение dp[o] = 1.

Порядок действий для нахождение dp[i]:

1. получаем значение из a[ i ]
2. циклом проходимся  по элементам начиная  с i до 0
3. если находим значение a[ j ] меньшее нашего, получаем длину его подпоследовательности как dp[ j ]
4. в dp[ i ] заносим максимальное из найденных значений в п.3 с “+ 1”

Алгоритм сложность O(n log n):

1. создадим дополнительный массив dp длины N (длина входного массива a): нулевой элемент ставим  -INF, остальные INF ( dp = [-inf, inf, inf, …].)
2. получаем dp[ i ], i - длина последовательности,  dp[ i ] - значение последнего элемента этой последовательности
3. благодаря такой структуре все значения в dp будут хранится в отсортированном порядке, ведь чем больше значение, тем больше элементов могут поместиться перед ним 4)  проходимся по a[] и  бинарным поиском находим такое k, что (dp[k-1] < x && dp[k] >= x) и присваиваем dp[k] значение x
4. ответ, это наибольший индекс массива dp отличный от INF