最后更新于3年前
用dp[i]表示s[0...i]最长的子序列长度,遍历s[0...i],若有0 <= j < i使得序列s[0...j]与s[i]构成更长的上升子序列,则更新dp。即当nums[i] > nums[j]时,dp[i] = max(dp[i], dp[j]+1)
dp[i]
s[0...i]
0 <= j < i
s[0...j]
s[i]
nums[i] > nums[j]
dp[i] = max(dp[i], dp[j]+1)
最后求dp数组的最大值
class Solution: def lengthOfLIS(self, nums ) -> int: n = len(nums) maxLen = 0 #dp数组中最大值 dp = [1] * n for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i], dp[j]+1) maxLen = max(maxLen, dp[i]) # 每得出一个dp[i],就比较更新 return maxLen