模版题-动态规划-最长递增子序列( 动态规划的应用场景 )
- 版权声明：本站原创文章，于2026-06-01，由 管理员 发表。
- 转载请注明： 模版题-动态规划-最长递增子序列( 动态规划的应用场景 ) | CodeGarden
```python
class Solution:
# 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
# 子序列是由数组派生而来的序列，
# 删除（或不删除）数组中的元素而不改变其余元素的顺序。
# 例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
# 1 <= nums.length <= 2500
# -10e4 <= nums[i] <= 10e4
def lengthOfLIS(self, nums: List[int]) -> int:
n = len( nums )
if n == 0 or n == 1: return n
# 每个元素有两种状态: 删除;保留
# 暴力: 枚举所有元素的各个状态排列 选择其中序列最长的严格递增子序列
# 再次重申: 对于这种暴力回溯枚举状态的题目 一般都可以用动态规划优化
# dp[ i ]表示以nums[ i ]结尾的最长数组的严格递增子序列长度
dp = [ 1 for _ in range( n ) ]
ans = 0
for i in range( n ):
# 从i-1向前寻找小于自己的数 取最大序列长度
max_ = 0
for j in range( i - 1, -1, -1 ):
if nums[ i ] > nums[ j ]:
if dp[ j ] > max_: max_ = dp[ j ]
dp[ i ] += max_
# 以nums[ n-1 ]结尾的最长严格递增子序列长度
# 不一定是nums中元素结尾的最长严格递增子序列长度
if dp[ i ] > ans: ans = dp[ i ]
return ans
```