ค้นหาลำดับบิตโทนิกที่ยาวที่สุด โดยที่ส่วนที่เพิ่มขึ้นและลดลงมาจากอาร์เรย์ที่แตกต่างกันสองชุดใน 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, ซ้าย, ขวา, คีย์

• ขณะที่ขวา - ซ้าย> 1 ทำ

  • กลาง :=ซ้าย +(ขวา - ซ้าย) / 2;

  • ถ้า arr[T[mid]]>=key แล้ว

    • ขวา :=กลาง

  • มิฉะนั้น

    • ซ้าย :=กลาง

• กลับขวา

• กำหนดฟังก์ชัน long_inc_seq() นี่จะใช้เวลา A

• n :=ขนาดของ A

• tails_idx :=อาร์เรย์ขนาด n เติม 0

• prev_idx :=อาร์เรย์ขนาด n เติม -1

• ความยาว :=1

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • ถ้า A[i]

    • tails_idx[0] :=ผม

  • มิฉะนั้นเมื่อ A[i]> A[tails_idx[length - 1]] แล้ว

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

    • tails_idx[ความยาว] :=ผม

    • ความยาว :=ความยาว + 1

  • มิฉะนั้น

    • ตำแหน่ง :=index_ceiling(A, tails_idx, -1, length - 1, A[i])

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

    • tails_idx[pos] :=ผม

• ผม :=tails_idx[ความยาว - 1]

• ในขณะที่ i>=0, ทำ

  • ใส่ A[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]