输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
动态规划还是找到传递方程，每次还是得想半天。
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
# 1. 递推公式
# dp[i] = max(dp[k] + [nums[i]]) if 存在k<i且dp[k]的最大值<nums[i]
# 否则 dp[i] = [nums[i]]
# 2. 完成条件
# i = len(nums)-1
# 3. 边界条件
# i = 0
num = len(nums)
if num == 0:
return 0
# (最大值, 长度)
dp = [0]*num
dp[0] = 1
res = 1
for i in range(1, num):
v = nums[i]
length_i = 0
# 找到比nums[i]小的j，且dp[i]最大的，可以考虑优化
# 参考答案：
# 新建数组 cell，用于保存最长上升子序列。
# 如果 cell 中元素都比它小，将它插到最后
# 否则，用它覆盖掉比它大的元素中最小的那个
# 保证了最大长度的最大值
# https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-e/
for j in range(0, i):
max_v = nums[j]
length = dp[j]
if v > max_v:
length_i = max(length_i, length+1)
if length_i == 0:
dp[i] = 1
else:
dp[i] = length_i
res = max(res, dp[i])
# print(i)
# print(dp)
return res
