0300.最长递增子序列
难度：🟡 中等
标签：数组、动态规划、二分查找
链接：300. 最长递增子序列
题目描述
给你一个整数数组 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
解题思路
核心思想
本题的目标是找到数组中“最长”的“递增”“子序列”。这是一个经典的动态规划问题。核心思想是定义一个状态，通过解决子问题来构建最终的解。
思路选择
动态规划 (Dynamic Programming) 是解决此问题的标准思路。
我们可以定义一个
dp数组，其中dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。为了计算
dp[i]，我们需要回顾在i之前的所有元素nums[j]（其中j < i）。如果
nums[j] < nums[i]，这意味着nums[i]可以接在以nums[j]结尾的递增子序列的后面，形成一个更长的递增子序列。因此，我们可以更新dp[i]的值为max(dp[i], dp[j] + 1)。遍历完所有可能的
j之后，dp[i]就得到了最终值。整个
dp数组中的最大值，就是整个nums数组的最长递增子序列的长度。
关键步骤
处理边界情况：如果数组为空，返回 0。
初始化：创建一个与
nums等长的dp数组，并用1填充。因为每个元素自身都构成一个长度为 1 的递增子序列。双层循环： a. 外层循环遍历
i从 1 到nums.length - 1。 b. 内层循环遍历j从 0 到i - 1。 c. 在内层循环中，如果nums[j] < nums[i]，则更新dp[i] = Math.max(dp[i], dp[j] + 1)。返回结果：遍历结束后，
dp数组中的最大值即为所求答案。
代码实现
/**
* @param {number[]} nums
* @return {number}
*/
var lengthOfLIS = function (nums) {
if (nums.length === 0) {
return 0;
}
// dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
let dp = new Array(nums.length).fill(1);
let maxLength = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
// 更新全局最长长度
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
};
复杂度分析
时间复杂度：O(n²) 其中 n 是数组
nums的长度。我们使用了两层嵌套循环。空间复杂度：O(n) 我们需要一个与输入等长的
dp数组来存储中间状态。
相关题目
总结
本题是动态规划领域的经典问题。O(n²) 的解法清晰地展示了如何通过定义状态和状态转移方程来解决问题。此外，本题还存在一个更为高效的 O(n log n) 解法，它通过维护一个有序的“牌堆”数组并结合二分查找来优化状态的更新过程，是进一步深入学习的绝佳案例。