题解 | #最长上升子序列(一)#
最长上升子序列(一)
https://www.nowcoder.com/practice/5164f38b67f846fb8699e9352695cd2f
class Solution:
def LIS(self, arr: List[int]) -> int:
n = len(arr)
if n == 0:
return 0
dp = [1] * n # 初始化dp数组，每个元素至少可以单独成为一个子序列
for i in range(1, n):
for j in range(i):
if arr[i] > arr[j]:
dp[i] = max(dp[i], dp[j] + 1) # 更新dp[i]为以arr[i]结尾的最长上升子序列长度
return max(dp) # 返回dp数组中的最大值，即最长上升子序列的长度
查看18道真题和解析