Напишите функцию на 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], и выведет ее в консоль.

🔗 Python tricks