পাইথনে দুটি অ্যারে থেকে সর্বোচ্চ বিটোনিক সিকোয়েন্স বের করা

ধরা যাক দুটি অ্যারে আছে। আমাদের সর্বোচ্চ দৈর্ঘ্যের বিটোনিক সিকোয়েন্স বের করতে হবে যাতে বৃদ্ধিশীল অংশ প্রথম অ্যারে থেকে এবং হ্রাসশীল অংশ دوم অ্যারে থেকে আসে। উভয় অংশ নিজস্ব অ্যারে-এর সাবসিকোয়েন্স হতে হবে।

যেমন, A=[2,6,3,5,4,6], B=[9,7,5,8,4,3] হলে আউটপুট [2,3,4,6,9,7,5,4,3]।

সমাধানের ধাপসমূহ (LIS + রিভার্স)

• index_ceiling(arr, T, left, right, key) ফাংশন: বাইনারি সার্চ দিয়ে সিলিং খুঁজুন
• long_inc_seq(A) ফাংশন: O(n log n) LIS অ্যালগরিদম (patience sorting) ব্যবহার করে বৃদ্ধিশীল সিকোয়েন্স বের করুন এবং answer-এ যোগ করুন
• মেইন ফাংশনে: long_inc_seq(A); answer রিভার্স করুন; B রিভার্স করুন; long_inc_seq(B); answer রিটার্ন করুন

উদাহরণ

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):
    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]