最长上升子序列（LIS）问题
最长上升子序列问题是动态规划中的一个经典问题。给定一个无序的整数数组，要求找到数组中最长的上升子序列的长度。一个上升子序列是指原数组的一个子序列，其中任意两个相邻的元素都满足后一个元素大于前一个元素。
算法思想
在解决LIS问题时，可以采用动态规划的思想。我们定义一个数组dp，其中dp表示以nums结尾的最长上升子序列的长度。对于数组中的每个元素nums，我们遍历它之前的所有元素nums（其中j < i），如果nums < nums，则说明nums可以接在nums后面形成一个更长的上升子序列。因此，我们更新dp为dp + 1和dp中的较大值。最后，遍历dp数组找到其中的最大值，即为所求的最长上升子序列的长度。
算法步骤
初始化一个与输入数组nums等长的数组dp，所有元素初始值为1（因为每个元素至少可以单独构成一个长度为1的上升子序列）。
遍历数组nums，对于每个元素nums，再遍历它之前的所有元素nums（其中j < i）。
如果nums < nums，则更新dp = max(dp, dp + 1)。
遍历完所有元素后，找到dp数组中的最大值，即为最长上升子序列的长度。
示例
输入数组：
初始化dp =
遍历nums，更新dp：
对于nums = 6，比较前面的nums = 2，因为2 < 6，所以dp = dp + 1 = 2
对于nums = 1，前面的元素都比它大，所以dp保持为1
对于nums = 9，比较前面的元素，dp更新为dp + 1 = 3（因为以6结尾的子序列最长为2，接上9后长度为3）
最终dp = ，最长上升子序列的长度为3。
这就是一种在一维数据结构上应用“套娃”思想（即嵌套或迭代求解）的算法示例。不过请注意，“一维套算法”并不是标准术语，这里只是为了解释而构造的一个表述。
页:
[1]