मान लीजिए हमारे पास दो सरणियाँ हैं; हमें सबसे लंबा संभव बिटोनिक अनुक्रम ढूंढना है ताकि बढ़ता हुआ भाग पहली सरणी से हो और पहली सरणी का उपअनुक्रम हो। इसी तरह घटता हुआ भाग दूसरी सरणी से होना चाहिए और दूसरी सरणी का उपअनुक्रम होना चाहिए।
तो, यदि इनपुट 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)
उत्तर := उत्तर उल्टा करें
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]
