34: Longest increasing subsequence

Дан массив чисел, найдите длину наибольшей возрастающей подпоследовательности (LIS)

 

Пример 1

Input: [3, 2, 9, 4, 10, 11, 7]

Output: 4

Пояснение: [3, 9, 10, 11] или [2, 9, 10, 11]

Пример 2

Input: [3, 2, 1]

Output: 1