300. 最长递增子序列
已解答
中等
相关标签
相关企业
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列
。
class Solution(object):def lengthOfLIS(self, nums):""":type nums: List[int]:rtype: int"""# f(i)定义为以i结尾的最长子序列长度sub_list=[1]for i in range(1,len(nums)):tmp = 1for j in range(i):if nums[i] > nums[j]:if sub_list[j]+1 > tmp:tmp=sub_list[j]+1sub_list.append(tmp)# print(sub_list)return max(sub_list)最重要的一点就是地推公式的定义，我们定义的是以n结尾的最长子序列