# 300. 最长上升子序列

[https://leetcode-cn.com/problems/longest-increasing-subsequence/](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数组的最大值

```python
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
```
