5317. 递增子序列（Increasing Subsequence）
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给你一个包含 n 个整数的数组，你的任务是找出其中的最长递增子序列（LIS）。 递增子序列是指每个元素都大于前一个元素的一个子序列。子序列可以从原数组中删除一些元素得到，但不改变剩余元素的相对顺序。 ## 输入格式 第一行包含一个整数 n：数组的大小。 第二行有 n 个整数 x₁, x₂, \dots, xₙ：表示数组中的元素。 ## 输出格式 输出最长递增子序列的长度。 ## 输入输出样例 ### 输入 #1 ``` 8 7 3 5 3 6 2 9 8 ``` ### 输出 #1 ``` 4 ``` ## 说明/提示 ### 数据规模与约定 - 1 \le n \le 2 · 10⁵ - 1 \le xᵢ \le 10⁹