LeetCode-热题100：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
提示：
- 1 <= nums.length <= 2500
- -104 <= nums[i] <= 104
代码及注释
func lengthOfLIS(nums []int) int {// 创建一个动态规划数组 dp，其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度dp := make([]int, len(nums))// 初始化结果为 1，因为每个单独的元素本身就是一个长度为 1 的上升子序列res := 1// 初始化 dp 数组的第一个元素为 1dp[0] = 1// 遍历整个数组for i := 1; i < len(nums); i++ {// 初始化 dp[i] 为 1，因为单个元素本身就是一个长度为 1 的上升子序列dp[i] = 1// 遍历当前元素之前的所有元素for j := 0; j < i; j++ {// 如果当前元素大于前面的某个元素，且加入当前元素后能构成更长的上升子序列if nums[i] > nums[j] {// 更新 dp[i]，取当前的 dp[i] 和 dp[j] + 1（加入当前元素后的长度）的较大值dp[i] = max(dp[i], dp[j] + 1)}}// 更新结果 res，取当前的 res 和 dp[i] 的较大值res = max(res, dp[i])}// 返回结果 res，即最长的上升子序列的长度return res
}// 辅助函数，返回两个整数中的较大值
func max(a, b int) int {if a > b {return a}return b
}
代码解释
动态规划数组 dp
在这个问题中，我们使用动态规划来解决。我们定义了一个 dp 数组，其中 dp[i] 表示以 nums[i] 结尾的最长上升子序列的长度。通过这种方式，我们可以迭代地计算更长的上升子序列，并找到最长的一个。
1.初始化
- 初始化
dp[0]为 1，因为单个元素本身就是一个长度为 1 的上升子序列。
2.状态转移
-
对于每个
nums[i]，我们需要检查之前的所有元素nums[j]（j < i）。如果nums[i] > nums[j]，则说明我们可以将nums[i]加入到以nums[j]结尾的子序列中，从而构成一个更长的上升子序列。 -
因此，我们更新
dp[i] = max(dp[i], dp[j] + 1)。
3.更新结果
- 每次更新
dp[i]后，我们都更新全局的最长上升子序列长度res。