class Solution:

    def lengthOfLIS(self,nums):

        if not nums:return 0                    #边界处理

        dp = [1 for _ in range(len(nums))]      #转态的定义，dp[i]表示当前时刻的最长升序列的值

        for i in range(len(nums)):              #第一次从前向后遍历

            for j in range(i):                  #从0到当前时刻遍历

                if nums[j] < nums[i]:           #如果出现升序的情况

                    dp[i] = max(dp[i],dp[j]+1)  #状态转移为当前时刻与之前时刻+1的最大值作为当前的状态

        print(dp)

        return max(dp)

if __name__ == '__main__':

    solution = Solution()

    nums = [10,9,2,5,3,7,101,18]                #结果是[2,3,7,101] 长度为4

    res = solution.lengthOfLIS(nums)

    print('最长序列：',res)