7-2 最长递增子序列 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
时间: 2024-04-01 11:36:56 浏览: 119
最长递增子序列
这是一道经典的动态规划问题,可以使用动态规划算法来解决。
具体的做法是:定义一个数组 dp,其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始化时,将 dp 数组全部初始化为 1,因为每个元素都可以单独成为一个递增子序列。
接下来,遍历数组 nums,对于每个元素 nums[i],再遍历它前面的元素 nums[j],如果 nums[j] 小于 nums[i],则可以将 nums[i] 接到 nums[j] 的后面形成一个更长的递增子序列,此时更新 dp[i] 的值为 dp[j]+1 和 dp[i] 中的较大值。
最后,遍历 dp 数组,找到其中的最大值即为最长递增子序列的长度。
以下是代码实现:
阅读全文