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

最长上升子序列(一)，动态规划

当前的元素，只有与之前的某个元素相接时才能组成最长上升子序列。只要之前元素比当前元素小，就可以相接，但最终与谁相接，则要看以谁结尾的上升子序列最长。相接即状态转移，若以元素i结尾的最长上升子序列长度为状态dp[i]，则它可能与之前i-1个状态相关，需遍历取满足条件的最大者作为其前一个状态。

class Solution:
    def LIS(self , arr: List[int]) -> int:
        if not arr: return 0
        dp = [1]*len(arr)          # 长度至少为1，故初始为1，dp[i]表示以arr[i]结尾的最长上升子序列
        max_len = 0                # 维护最长值
        for i in range(len(arr)):
            j = i
            tmp = 0
            while j >= 0:         # 往前找尾部值比arr[i]小的最长上升子序列
                if arr[i] > arr[j]:
                    tmp = max(tmp, dp[j]) 
                j -= 1
            dp[i] += tmp          # 初始值1，加上之前的最长长度
            max_len = max(max_len, dp[i])
        return max_len