# README

300. Longest Increasing Subsequence

Level - medium

Task

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Объяснение

Задача требует от нас найти длину самой длинной возрастающей подпоследовательности (LIS) в заданном массиве целых чисел. Подпоследовательность — это последовательность, которая может быть получена из исходной последовательности путем удаления некоторых элементов (возможно, ни одного) без изменения порядка оставшихся элементов.

Примеры:

Входной массив: [10, 9, 2, 5, 3, 7, 101, 18] Самая длинная возрастающая подпоследовательность: [2, 3, 7, 101] Длина LIS: 4
Входной массив: [0, 1, 0, 3, 2, 3] Самая длинная возрастающая подпоследовательность: [0, 1, 2, 3] Длина LIS: 4
Входной массив: [7, 7, 7, 7, 7, 7, 7] Самая длинная возрастающая подпоследовательность: [7] Длина LIS: 1

Какие я вижу подходы к решению задачи:

Динамическое программирование
Бинарный поиск и динамическое программирование.

Эти подходы позволяют эффективно решить задачу с разными временными сложностями: O(n^2) для первого подхода и O(n log n) для второго подхода.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints:

1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4