Напишите функцию на Python, которая принимает на вход список чисел и возвращает наибольшую возрастающую подпоследовательность (непоследовательные числа, идущие в порядке возрастания) из исходного списка
Для решения этой задачи используется динамическое программирование. Мы создаем массив dp, где dp[i] представляет собой длину наибольшей возрастающей подпоследовательности, заканчивающейся в nums[i]. Затем мы выполняем двойной цикл, чтобы найти наибольшую длину для каждого элемента. После этого мы определяем саму подпоследовательность, начиная с наибольшей длины и двигаясь обратно по массиву dp.
Пример использования:
python
nums = [3, 12, 5, 8, 10, 2, 1]
result = longest_increasing_subsequence(nums)
print(result) # Output: [3, 5, 8, 10]
Эта функция найдет наибольшую возрастающую подпоследовательность из списка [3, 12, 5, 8, 10, 2, 1], которой будет [3, 5, 8, 10], и выведет ее в консоль.
Для решения этой задачи используется динамическое программирование. Мы создаем массив dp, где dp[i] представляет собой длину наибольшей возрастающей подпоследовательности, заканчивающейся в nums[i]. Затем мы выполняем двойной цикл, чтобы найти наибольшую длину для каждого элемента. После этого мы определяем саму подпоследовательность, начиная с наибольшей длины и двигаясь обратно по массиву dp.
Пример использования:
python
nums = [3, 12, 5, 8, 10, 2, 1]
result = longest_increasing_subsequence(nums)
print(result) # Output: [3, 5, 8, 10]
Эта функция найдет наибольшую возрастающую подпоследовательность из списка [3, 12, 5, 8, 10, 2, 1], которой будет [3, 5, 8, 10], и выведет ее в консоль.