题解 | #最长上升子序列(一)#

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数组中的最大值，即最长上升子序列的长度