当前位置：首页 > 文章列表 > 文章 > 前端 > LeetCode冥想：最长递增子序列

LeetCode冥想：最长递增子序列

来源：dev.to 2024-12-11 21:21:54 0浏览收藏

哈喽！大家好，很高兴又见面了，我是golang学习网的一名作者，今天由我给大家带来一篇《LeetCode冥想：最长递增子序列》，本文主要会讲到等等知识点，希望大家一起学习进步，也欢迎大家关注、点赞、收藏、转发! 下面就一起来看看吧！

LeetCode冥想：最长递增子序列

这个问题的描述简单地说：

给定一个整数数组 nums，返回最长严格递增子序列.
的长度

例如：

input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
output: 4
explanation: 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 从索引开始可以拥有的最大子序列的数量 $i 1 i 1$ 。

但是，如果 nums[i 1] 小于 nums[i]，我们不能包含第二个选项。

首先，我们可以首先创建一个 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);
}