查找最长的双音序列，以便增加和减少部分来自Python中的两个不同数组
假设我们有两个数组；我们必须找到最长的双音序列，以便增加的部分应该来自第一个数组，并且应该是第一个数组的子序列。同样，的递减部分必须来自第二个数组和第二个数组的子序列。
因此，如果输入像A=[2、6、3、5、4、6]，B=[9、7、5、8、4、3]，那么输出将为[2、3、4，6，9，7，5，4，3]
为了解决这个问题，我们将遵循以下步骤-
定义一个函数index_ceiling()。这将需要arr，T，左，右，键
而右-左>1，则
左：=中
右：=中
中：=左+（右-左）/2;
如果arr[T[mid]]>=键，则
除此以外，
归还权利
定义一个函数long_inc_seq()。这需要一个
n：=A的大小
tails_idx：=大小为n的数组，用0填充
prev_idx：=大小为n的数组，用-1填充
长度：=1
对于1到n范围内的i，执行
pos：=index_ceiling（A，tails_idx，-1，长度-1，A[i]）
prev_idx[i]：=tails_idx[pos-1]
tails_idx[pos]：=i
prev_idx[i]：=tails_idx[length-1]
tails_idx[length]：=i
长度：=长度+1
tails_idx[0]：=i
如果A[i]<A[tails_idx[0]]，则
否则，当A[i]>A[tails_idx[length-1]]时，则
除此以外，
i：=tails_idx[length-1]
当我>=0时
在答案的末尾插入A[i]
i：=prev_idx[i]
从主要方法中，执行以下操作-
n1：=A的大小，n2：=B的大小
long_inc_seq(A)
答案：=反向答案
B：=反向B
long_inc_seq(B)
返回答案
示例
让我们看下面的实现以更好地理解-
answer = []
def index_ceiling(arr,T, left,right, key):
while (right - left > 1):
mid = left + (right - left) // 2;
if (arr[T[mid]] >= key):
right = mid
else:
left = mid
return right
def long_inc_seq(A):
n = len(A)
tails_idx = [0]*(n)
prev_idx = [-1]*(n)
length = 1
for i in range(1, n):
if (A[i] < A[tails_idx[0]]):
tails_idx[0] = i
elif (A[i] > A[tails_idx[length - 1]]):
prev_idx[i] = tails_idx[length - 1]
tails_idx[length] = i
length += 1
else:
pos = index_ceiling(A, tails_idx, -1, length - 1, A[i])
prev_idx[i] = tails_idx[pos - 1]
tails_idx[pos] = i
i = tails_idx[length - 1]
while(i >= 0):
answer.append(A[i])
i = prev_idx[i]
def long_bitonic(A,B):
n1 = len(A)
n2 = len(B)
global answer
long_inc_seq(A)
answer = answer[::-1]
B = B[::-1]
long_inc_seq(B)
A = [2, 6, 3, 5, 4, 6]
B = [9, 7, 5, 8, 4, 3]
long_bitonic(A,B)
print(answer)输入值
[2, 6, 3, 5, 4, 6], [9, 7, 5, 8, 4, 3]
输出结果
[2, 3, 4, 6, 9, 7, 5, 4, 3]