Computer >> Máy Tính >  >> Lập trình >> Python

Tìm chuỗi bitonic dài nhất sao cho các phần tăng và giảm từ hai mảng khác nhau trong Python

Giả sử chúng ta có hai mảng; chúng ta phải tìm dãy bitonic dài nhất có thể để phần tăng dần phải từ mảng đầu tiên và phải là dãy con của mảng đầu tiên. tương tự giảm một phần của phải từ mảng thứ hai và một dãy con của mảng thứ hai.

Vì vậy, nếu đầu vào là A =[2, 6, 3, 5, 4, 6], B =[9, 7, 5, 8, 4, 3], thì đầu ra sẽ là [2, 3, 4 , 6, 9, 7, 5, 4, 3]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

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)

Đầu vào 

[2, 6, 3, 5, 4, 6], [9, 7, 5, 8, 4, 3]

Đầu ra 

[2, 3, 4, 6, 9, 7, 5, 4, 3]