什么叫最长递增子序列

最长递增子序列是指在一个序列中找到一个子序列，使得子序列中的元素按照顺序递增，并且这个子序列的长度最长。例如，对于序列 [3, 1, 4, 1, 5, 9, 2, 6, 5]，其中的最长递增子序列是 [1, 4, 5, 9]，长度为 4。

求解最长递增子序列的问题可以使用动态规划算法来解决。定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。初始时，将 dp 数组所有元素初始化为 1，然后从左到右遍历原始序列，对于每个元素 nums[i]，再从序列的开头到当前元素之前的元素进行遍历。如果 nums[i] 大于之前的某个元素 nums[j]，则更新 dp[i] = max(dp[i], dp[j]+1)，表示以第 i 个元素结尾的最长递增子序列长度为之前某个元素结尾的最长递增子序列长度加一。

最后，遍历 dp 数组找到最大值即可得到最长递增子序列的长度。

需要注意的是，以上方法只能得到最长递增子序列的长度，并不能得到具体的子序列。如果需要得到具体的子序列，可以在动态规划过程中记录每个 dp[i] 的最大值对应的前一个元素的索引，然后再根据这些索引从后往前进行回溯获取子序列。