leetcode hot 100 最长递增子序列
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 = 1
for j in range(i):
if nums[i] > nums[j]:
if sub_list[j]+1 > tmp:
tmp=sub_list[j]+1
sub_list.append(tmp)
# print(sub_list)
return max(sub_list)
最重要的一点就是地推公式的定义，我们定义的是以n结尾的最长子序列