Longest Subsequence¶
HEADING¶
300. Longest Increasing Subsequence (Medium)¶
def lengthOfLIS(self, nums: List[int]) -> int:
@lru_cache(maxsize=None)
def rec(i):
if i >= len(nums):
return 1
maxi = 1
for j in range(i, len(nums)):
if nums[i] < nums[j]:
maxi = max(maxi, 1 + rec(j))
return maxi
dp = [rec(i) for i in range(len(nums))]
return max(dp)
def lengthOfLIS(self, nums: List[int]) -> int:
def rec(i):
if i >= n:
return 1
elif dp[i]:
return dp[i]
maxi = 1
for j in range(i, n):
if nums[i] < nums[j]:
maxi = max(maxi, 1 + rec(j))
dp[i] = maxi
return dp[i]
n = len(nums)
dp = [None] * n
for i in range(n - 1, -1, -1):
rec(i)
return max(dp)
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = [None] * n
for i in range(n - 1, -1, -1):
maxi = 1
for j in range(i, n):
if nums[i] < nums[j]:
maxi = max(maxi, 1 + dp[j])
dp[i] = maxi
print(dp)
return max(dp)
def lengthOfLIS(self, nums: List[int]) -> int:
sub = [nums[0]]
for num in nums[1:]:
if num > sub[-1]:
sub.append(num)
else:
ind = bisect.bisect_left(sub, num)
sub[ind] = num
return len(sub)