在 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
对于范围为 1 到 n 的 i,执行
如果 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 时,执行
在 answer 末尾插入 A[i]
i := prev_idx[i]
从 main 方法中,执行以下操作 −
n1 := A 的大小,n2 := B 的大小
long_inc_seq(A)
answer := reverse answer
B := reverse 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]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

