这个问题的描述简单地说：
给定一个整数数组 nums，返回最长严格递增子序列.的长度
例如：
input: nums = [10, 9, 2, 5, 3, 7, 101, 18]output: 4explanation: the longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.
或者：
input: nums = [0, 1, 0, 3, 2, 3]output: 4
或者：
input: nums = [7, 7, 7, 7, 7, 7, 7]output: 1
与本系列的上一个问题类似，我们也可以在这里看看自下而上的动态规划方法。
对于 nums 数组中的每个值，我们可以从索引开始的最大子序列的长度 我我我 是：
1（该值本身）
或
1 从索引开始可以拥有的最大子序列的数量 i1i 1 i 1。
但是，如果 nums[i 1] 小于 nums[i]，我们不能包含第二个选项。
腾讯云AI代码助手
172 查看详情
首先，我们可以首先创建一个 dp 数组来保存从 nums 的每个索引开始可以拥有的子序列的长度。也就是说，dp[0] 的长度是从 nums[0] 开始的最大子序列的长度，dp[1] 的长度是从 nums[1] 开始的最大子序列的长度，等等于：
let dp = array.from({ length: nums.length }, () => 1);
然后，我们可以从 nums 的最后一个索引开始向后迭代（因为这是最简单的位置，只有一种方法可以向前形成子序列，只需取值本身）：
for (let i = nums.length - 1; i >= 0; i--) { /* ... */}
对于每个选项，我们可以从下一个索引开始迭代，看看是否可以包含从该索引开始可以形成的最大子序列，如果可以，我们可以得到 dp[i] 和 1 dp 之间的最大值[j]：
for (let i = nums.length - 1; i >= 0; i--) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] < nums[j]) { dp[i] = math.max(dp[i], 1 + dp[j]); } }}
最后，我们可以返回 dp 中的最大值：
function lengthoflis(nums: number[]): number { /* ... */ return math.max(...dp); }
最终的解决方案如下所示：
function lengthOfLIS(nums: number[]): number { let dp = Array.from({ length: nums.length }, () => 1); for (let i = nums.length - 1; i >= 0; i--) { for (let j = i + 1; j < nums.length; j++) { if (nums[i] < nums[j]) { dp[i] = Math.max(dp[i], 1 + dp[j]); } } } return Math.max(...dp);}
时间和空间复杂度
时间复杂度为 o(n2)o(n ^2) o(n2） 当我们迭代 nums 中的每个项目时，对于 nums 中的每个项目。
空间复杂度为 o(n)o(n) o(n) 因为我们保留了一个 dp 数组，它的大小会随着 nums 长度的增加而增加。
这是本系列中的最后一个动态规划问题。接下来，我们将开始关于间隔的新篇章。在那之前，祝您编码愉快。
以上就是LeetCode冥想：最长递增子序列的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/784103.html
微信扫一扫 
支付宝扫一扫 
