class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
dp = [1]
for i in range(1, n):
max_seq = 1
for j in range(i):
if nums[i] > nums[j]:
max_seq = max(max_seq, dp[j] + 1)
dp.append(max_seq)
return max(dp)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
mins = []
for num in nums:
index = bisect.bisect_left(mins, num)
if index == len(mins):
mins.append(num)
else:
mins[index] = num
return len(mins)
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
if n == 0:
return 0
A = list(set(nums))
A.sort()
A = [0] + A
mapping = {num: i for i, num in enumerate(A)}
C = [0] * len(A)
final_max = 0
for num in nums:
index = mapping[num] - 1 # 严格递增, 从第一个小于此数的位置找起
current_max = 0
while index > 0:
current_max = max(current_max, C[index])
index -= index & (-index)
final_max = max(final_max, current_max + 1)
# 修改
index = mapping[num]
while index < len(A):
C[index] = max(C[index], current_max + 1)
index += index & (-index)
return final_max