文章目录
- 最长递增子序列
- 思路一
最长递增子序列
给你一个整数数组 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
思路一
function lengthOfLIS(nums) {if (nums.length === 0) return 0;const dp = new Array(nums.length).fill(1); // 初始化dp数组，每个元素的初始值为1// 遍历数组，更新dp数组for (let i = 1; i < nums.length; i++) {for (let j = 0; j < i; j++) {if (nums[i] > nums[j]) {// 更新dp[i]，使其成为以nums[i]结尾的最长递增子序列长度dp[i] = Math.max(dp[i], dp[j] + 1);}}}// 找到dp数组中的最大值，即为最长递增子序列的长度return Math.max(...dp);
}
// 这段代码首先定义了lengthOfLIS函数，它接收一个整数数组nums作为输入，然后使用动态规划的方法计算并返回最长严格递增子序列的长度。通过两层循环，外层循环遍历数组，内层循环寻找可以与当前元素构成递增子序列的之前元素，并更新dp数组。最后，从dp数组中找到最大值作为答案返回。
讲解
这道题可以使用动态规划（Dynamic Programming, DP）的方法来解决。基本思路是创建一个长度与原数组相同的新数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长严格递增子序列的长度。初始时，dp 数组中的每个元素都为 1，因为至少每个元素自身都可以构成一个长度为 1 的递增子序列。
接下来，对于数组中的每个元素，我们检查它之前的所有元素。如果 nums[i] 大于 nums[j]（其中 j < i），那么我们可以考虑将 nums[i] 添加到以 nums[j] 结尾的递增子序列中，因此可能会得到一个更长的递增子序列。此时，我们尝试更新 dp[i] = Math.max(dp[i], dp[j] + 1)，表示以 nums[i] 结尾的最长子序列长度可能由以 nums[j] 结尾的子序列长度加 1 得到。
最后，遍历一遍 dp 数组，找到其中的最大值，即为原数组中最长严格递增子序列的长度。