华为 OD 训练营 · 题解精讲
LC300. 最长递增子序列
配套讲解：视频讲解 ↗
LC300. 最长递增子序列 视频地址：https://uha.xet.tech/s/20W7ji
题目描述
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。
题目解析
解题思路
本题采用动态规划求解。定义 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。对于每个位置 i，需要遍历它之前的所有位置 j（0 ≤ j < i），如果 nums[j] < nums[i]，则可以将 nums[i] 接在以 nums[j] 结尾的递增子序列后面，形成更长的子序列，长度为 dp[j] + 1。取所有可能中的最大值作为 dp[i]。最终答案为所有 dp[i] 中的最大值。
关键步骤
1. 初始化：dp 数组全部设为 1，因为每个元素自身可构成长度为 1 的子序列。 2. 双层循环：
- 外层
i从 1 到n-1，计算每个dp[i]。 - 内层
j从 0 到i-1，检查nums[j] < nums[i]是否成立。 - 若成立，则
dp[i] = max(dp[i], dp[j] + 1)。
3. 更新全局最大值：每计算完一个 dp[i]，更新 maxLength。
示意图（以 nums = [1,5,2,5,3,7,2] 为例，计算 dp[3] 时）：
索引: 0 1 2 3 4 5 6
nums: [1, 5, 2, 5, 3, 7, 2]
dp: [1, 2, 2, ?, ...]
↑ ↑
j=0 j=2
nums[0]=1 < 5, dp[0]+1=2 → dp[3]=2
nums[2]=2 < 5, dp[2]+1=3 → dp[3]=3
最终 dp[3]=3复杂度分析
- 时间复杂度：O(n²)，其中 n 为数组长度。双层循环，每层最多 n 次。
- 空间复杂度：O(n)，用于存储 dp 数组。
参考代码
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 设置数组 dp，用来存储 nums 中以每个元素结尾的最长递增序列的程度
# dp[0] 表示以 nums[0] 结尾的最长递增序列的长度
# dp[1] 表示以 nums[1] 结尾的最长递增序列的长度
# dp[i] 表示以 nums[i] 结尾的最长递增序列的长度
# 首先将数组 dp 里面的值都初始化为 1
# 1 表示以当前元素结尾的最长递增序列的长度为 1
# 即最长递增序列就是当前元素本身
dp = [ 1 for _ in range(len(nums))]
# 设置一个变量用来存储最长递增序列的结果
maxLength = 1
# 从 1 开始，直到 dp.length ，往 dp 里面填充结果
for i in range( 1 , len(dp) ) :
# 对于 dp[i] 来说，在 nums 中从 0 到 i - 1 都是在 i 的前面的
# 比如 nums 为 [1,5,2,5,3,7,2]
# 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
# 从 0 遍历到 i - 1，就可以从这些数字中选出小于 i 的数字
for j in range ( 0 , i ) :
# 索引 0 1 2 3 4 5 6
# nums 为 [ 1, 5, 2, 5, 3, 7, 2 ]
# 此时 i 为 3，那么 1,5,2 这些数字都在索引位置为 3 的前面
# 1、从这些数字中选出小于 nums[i] 的数字
# 2、小于 nums[i] 的那些数字是 1 , 2 ，在之前都已经计算过以 1 或者 2 结尾的最长递增序列的长度
# 并且这个结果存放在 dp[j] 中
# 如果数字为 1，那么此时 j 为 0，dp[0] 存放了以 1 结尾的最长递增序列的长度
# 如果数字为 2，那么此时 j 为 2，dp[2] 存放了以 2 结尾的最长递增序列的长度
# 3、如果发现此时 dp[i] 小于了 dp[j] + 1
# 4、说明此时 dp[i] 中的值就不是以 nums[i] 结尾的最长递增序列的长度
# 需要更新 dp[i]
if nums[i] > nums[j] and dp[i] < dp[j] + 1 :
# 4、更新 dp[i]
dp[i] = dp[j] + 1
# 在更新 dp[i] 的过程中，发现了一个更长的子序列
if maxLength < dp[i] :
# 那么把更长的子序列的长度赋值给 maxLength
maxLength = dp[i]
# 最后返回 maxLength 就行
return maxLength