题目
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
例：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
方法：动态规划
- 若整数数组 nums 的长度为 1，那么最长递增子序列即为该数字，长度为 1
- 同理，由于 dp[i] 表示 i 及 i 以前的组成的数组所拥有的最长递增子序列的长度，那么应将其初始化为 1 而非之前的 0
- result 表示此时（最终）的最长递增子序列的长度
- 外层循环即为对除第一个数字外的其他数字 i 从前到后的循环，而内层循环为对从第一个数字到 i-1 数字的循环。
- 若数字 nums[i] 大于此时的 nums[j]，及表示此时的数字 nums[i] 可以同 nums[j] 和与 nums[j] 组成最长递增序列的数字序列结合组成新的递增序列。通过对每个递增序列的长度进行对比，选择最长递增子序列，即得到 dp[i]
- 每结束一次内层循环，计算一次此时的最长递增子序列的长度 result
class Solution(object):
def lengthOfLIS(self, nums):
if len(nums) == 1:
return 1
dp = [1] * len(nums)
result = 0
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
result = max(result, dp[i])
return result
参考
代码相关：https://programmercarl.com/0300.%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97.html
