查找最长的双音序列，以便增加和减少部分来自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]