LeetCode300.最长递增子序列：动态规划详解

发布日期：2021年8月6日

问题描述及示例

给定一个整数数组 nums，找到其中最长的严格递增子序列，并返回其长度。子序列是从原数组中派生出来的序列，通过删除（或不删除）某些元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入: nums = [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长递增子序列是 [2,3,7,101]，因此长度为 4。

示例 2：
输入: nums = [0,1,0,3,2,3]
输出: 4

示例 3：
输入: nums = [7,7,7,7,7,7,7]
输出: 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

提示：
1 <= nums.length <= 2500
-10^4 <= nums[i] <= 10^4

解题思路

这是一道经典的动态规划问题。在初次接触时，可能会误以为需要使用递归或回溯方法来解决，但这些方法往往会导致时间复杂度过高。正确的方法是使用动态规划来降低时间复杂度。

动态规划解法

首先，定义一个 dp 数组，其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始时，每个元素的最长递增子序列长度至少为1，即 dp[i] = 1。

接下来，我们需要通过两层循环来填充 dp 数组：

• 外层循环遍历数组中的每个元素 nums[i]。
• 内层循环遍历 nums[i] 之前的每个元素 nums[j]，如果 nums[i] > nums[j]，则更新 dp[i] 的值为 dp[j] + 1 和当前 dp[i] 的最大值。

最终，dp 数组中的最大值即为所求的最长递增子序列的长度。

以下是具体的代码实现：

/** * @param {number[]} nums * @return {number} */ var lengthOfLIS = function(nums) { let dp = new Array(nums.length).fill(1); let result = 1; for (let i = 1; i  nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } result = Math.max(result, dp[i]); } return result; }; 

在上述代码中，内层循环用于确定 nums[i] 之前的最长递增子序列长度，并通过 Math.max 函数来更新 dp[i] 的值。外层循环结束后，result 即为最终结果。

常见错误分析

在初次尝试时，可能会出现一些常见的错误，例如错误地使用 dp 数组来存储子序列本身而不是其长度。这种误解会导致在处理特定输入时出现问题。例如，对于输入 nums = [0, 1, 0, 3, 2, 3]，错误的实现可能会返回 3 而不是 4。

为了避免这类错误，务必明确 dp[i] 的定义，并严格按照定义来更新 dp 数组。

其他解法

除了动态规划方法，还可以使用二分查找来进一步优化时间复杂度。这种方法的核心思想是维护一个有序数组，通过二分查找来更新该数组，从而快速找到最长递增子序列的长度。具体实现可以参考其他博主的分享和解析。

官方题解

由于版权问题，官方题解的具体代码不再粘贴。感兴趣的读者可以访问以下链接查看：
最长上升子序列 - 最长递增子序列 - 力扣（LeetCode）

参考资料

参考：【微信公众号：代码随想录 2021-03-09】动态规划：最长递增子序列