300. Longest Increasing Subsequence
https://leetcode.com/problems/longest-increasing-subsequence/
solution
dp
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
if not nums:
return
dp = [1] * len(nums) # dp[i]: 以nums[i]结尾的最长子序列
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)
return max(dp)
时间复杂度:O(n^2) 空间复杂度:O(n)
binary search
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
tails = []
for num in nums:
if not tails or num > tails[-1]:
tails.append(num)
else:
tails[bisect.bisect_left(tails, num)] = num
return len(tails)
时间复杂度:O(nlog(n)) 空间复杂度:O(n)
follow up
674 Longest Continuous Increasing Subsequence
最长连续递增序列,由于要求必须连续,因此只需要dp(i)与dp(i-1)比较即可
646. Maximum Length of Pair Chain
Last updated