सबसे लंबा बिटोनिक अनुक्रम खोजें जैसे कि बढ़ते और घटते हिस्से पायथन में दो अलग-अलग सरणियों से हों

मान लीजिए कि हमारे पास दो सरणियाँ हैं; हमें सबसे लंबा संभव बिटोनिक अनुक्रम खोजना होगा ताकि बढ़ता हुआ हिस्सा पहले सरणी से हो और पहली सरणी का बाद हो। इसी तरह घटते हुए हिस्से को दूसरे एरे से और दूसरे एरे के बाद का होना चाहिए।

इसलिए, यदि इनपुट ए =[2, 6, 3, 5, 4, 6], बी =[9, 7, 5, 8, 4, 3] जैसा है, तो आउटपुट [2, 3, 4] होगा। , 6, 9, 7, 5, 4, 3]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन को परिभाषित करें index_ceiling() । यह गिरफ्तारी, टी, बाएँ, दाएँ, कुंजी लेगा

• जबकि दाएं - बाएं> 1, करें

  • मध्य:=बाएँ + (दाएँ - बाएँ) / 2;

  • अगर गिरफ्तारी [टी [मध्य]]> =कुंजी, फिर

    • दाएं:=मध्य

  • अन्यथा,

    • बाएं :=मध्य

• दाएं लौटें

• एक फ़ंक्शन को परिभाषित करें long_inc_seq() । इसमें A

  . लगेगा

• n :=A का आकार

• tails_idx :=आकार n की एक सरणी, 0 से भरें

• prev_idx :=आकार n की एक सरणी, -1 से भरें

• लंबाई :=1

• 1 से n की सीमा में i के लिए, करें

  • अगर ए[i] <ए[tails_idx[0]], तो

    • tails_idx[0] :=i

  • अन्यथा जब A[i]> A[tails_idx[length - 1]], तब

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

    • tails_idx[लंबाई] :=i

    • लंबाई :=लंबाई + 1

  • अन्यथा,

    • स्थिति :=index_ceiling(A, tails_idx, -1, लंबाई -1, A[i])

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

    • tails_idx[pos] :=i

• मैं :=tails_idx[लंबाई - 1]

• जबकि मैं>=0, करते हैं

  • उत्तर के अंत में A[i] डालें

  • मैं :=prev_idx[i]

• मुख्य विधि से, निम्न कार्य करें -

• n1:=A का आकार, n2:=B का आकार

• long_inc_seq(ए)

• उत्तर :=उल्टा उत्तर

• बी:=रिवर्स बी

• long_inc_seq(बी)

• वापसी उत्तर

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

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]