转换为最长上升子序列问题 $O(nlogn)$
对于arr2中每个元素, 在arr1中寻找下标,得到arr3 = arr2’ 求最长上升子序列
求arr3的上升序列, 就相当于在arr1中找到了公共序列
LIS dp做法n^2; 如果二分+贪心, nlogn
python 代码
n = int(input())
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
#在arr2中每个元素 在arr1中寻找下标 得到arr3 = arr2' 求最长上升子序列 nlogn
#最长上升子序列 dp n^2; 二分+贪心, nlogn
dic = {}
for i,v in enumerate(arr1):
dic[v] = i
#print(dic)
arr3 = []
for j,num in enumerate(arr2):
#如果有arr1中未出现的,忽略
if num in dic:
arr3.append(dic[num])
#print(arr3)
#在生成的index序列, arr3中运用最长上升子序列: 贪心+二分. O(nlogn)
d = []
for num in arr3:
if not d or num > d[-1]:
d.append(num)
else:
l, r = 0, len(d) - 1
loc = r
while l <= r:
mid = (l + r) // 2
if d[mid] >= num:
loc = mid
r = mid - 1
else:
l = mid + 1
d[loc] = num
#print(d)
print(len(d))
'''
dp = [[0] * (n + 1) for _ in range(n + 1)]
#dp O(n^2) 过不了
for i in range(1, n + 1):
for j in range(1, n + 1):
if arr1[i - 1] == arr2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[n][n])
'''