দীর্ঘতম বিটোনিক ক্রম খুঁজুন যেমন ক্রমবর্ধমান এবং হ্রাস অংশগুলি পাইথনের দুটি ভিন্ন অ্যারে থেকে

ধরুন আমাদের দুটি অ্যারে আছে; আমাদের সম্ভাব্য দীর্ঘতম বিটোনিক ক্রমটি খুঁজে বের করতে হবে যাতে ক্রমবর্ধমান অংশটি প্রথম অ্যারের থেকে হওয়া উচিত এবং প্রথম অ্যারের পরবর্তী অংশ হওয়া উচিত। একইভাবে হ্রাসকারী অংশ অবশ্যই দ্বিতীয় অ্যারে থেকে এবং দ্বিতীয়টির পরবর্তী অংশ হতে হবে।

সুতরাং, যদি ইনপুটটি 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

  লাগবে

• ডানে - বামে> 1, করুন

  • মধ্য :=বাম +(ডান - বাম) / 2;

  • যদি arr[T[mid]]>=কী, তাহলে

    • ডান :=মধ্য

  • অন্যথায়,

    • বাম :=মধ্য

• ডানে ফিরুন

• একটি ফাংশন long_inc_seq() সংজ্ঞায়িত করুন। এটি A

  লাগবে

• n :=A

  এর আকার

• tails_idx :=n আকারের একটি অ্যারে, 0 দিয়ে পূরণ করুন

• prev_idx :=n আকারের একটি অ্যারে, -1 দিয়ে পূরণ করুন

• দৈর্ঘ্য :=1

• 1 থেকে n রেঞ্জের জন্য, করুন

  • যদি A[i]

    • tails_idx[0] :=i

  • অন্যথায় যখন A[i]> A[tails_idx[দৈর্ঘ্য - 1]], তারপর

    • prev_idx[i] :=tails_idx[দৈর্ঘ্য - 1]

    • tails_idx[দৈর্ঘ্য] :=i

    • দৈর্ঘ্য :=দৈর্ঘ্য + 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[দৈর্ঘ্য - 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]