在 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、left、right、key

  • 当 right - left > 1 时，执行

    • mid := left +(right - left) / 2;

    • 如果 arr[T[mid]] >= key，则

      • right := mid

    • 否则，

      • left := mid

  • 返回 right

  • 定义一个函数 long_inc_seq()。这将接收 A

  • n := A 的大小

  • tails_idx := 一个大小为 n 的数组，填充为 0

  • prev_idx := 一个大小为 n 的数组，填充为 -1

  • length := 1

  • 对于 i 的范围从 1 到 n，执行

    • 如果 A[i] < A[tails_idx[0]]，则

      • tails_idx[0] := i

    • 否则当 A[i] > A[tails_idx[length - 1]] 时，则

      • prev_idx[i] := tails_idx[length - 1]

      • tails_idx[length] := i

      • length := length + 1

    • 否则，

      • 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]

  • 当 i >= 0 时，执行

    • 将 A[i] 插入到答案的末尾

    • i := prev_idx[i]

  • 从主方法中，执行以下操作 -

  • n1 := A 的大小，n2 := B 的大小

  • long_inc_seq(A)

  • answer := 反转答案

  • B := 反转 B

  • long_inc_seq(B)

  • 返回 answer

示例

让我们看看以下实现以获得更好的理解 -

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]

更新于: 2020-08-25

91 次查看

开启您的 职业生涯

通过完成课程获得认证

立即开始
广告