62. 最长递增子序列.md

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        #dp[i]表示以nums[i]结尾的上升子序列的长度，nums[i]必须被选取，且必须为这个子序列的最后一个元素。
        n = len(nums)
        dp = [1]*n
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[j]+1, dp[i])
        return max(dp)