300.最长上升子序列.md

300. 最长上升子序列

https://leetcode-cn.com/problems/longest-increasing-subsequence/

解法一：dp

用dp[i]表示s[0...i]最长的子序列长度，遍历s[0...i]，若有0 <= j < i使得序列s[0...j]与s[i]构成更长的上升子序列，则更新dp。即当nums[i] > nums[j]时，dp[i] = max(dp[i], dp[j]+1)

最后求dp数组的最大值

class Solution:
     def lengthOfLIS(self, nums ) -> int:
        n = len(nums)
        maxLen = 0	#dp数组中最大值
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
            maxLen = max(maxLen, dp[i])		# 每得出一个dp[i]，就比较更新
        return maxLen