পাইথনে সবচেয়ে কম্পিটিটিভ সাবসিকোয়েন্স খুঁজে বের করার প্রোগ্রাম

মান লিজিয়ে একটি অ্যারে আছে nums এবং আরেকটি মান k, আমাদের nums-এর সাইজ k এর সবচেয়ে কম্পিটিটিভ সাবসিকোয়েন্স বের করতে হবে। এখানে একটি সাবসিকোয়েন্স s1 অন্যটি s2-এর চেয়ে বেশি কম্পিটিটিভ যদি প্রথম যেই পজিশনে s1 এবং s2 ভিন্ন হয়, সেখানে s1-এর সংখ্যা s2-এর চেয়ে ছোট হয়।

যেমন, ইনপুট হলে nums = [4,6,3,7], k = 2, তবে আউটপুট হবে [3,7] কারণ সাইজ ২-এর সব সাবসিকোয়েন্স গুলো: {[4,6], [4,3], [4,7], [6,3], [6,7], [3,7]}, এখানে [3,7] সবচেয়ে কম্পিটিটিভ।

সমাধানের ধাপসমূহ

• attempts := len(nums) - k

• stack := নতুন লিস্ট

• nums-এ প্রতিটি num এর জন্য:

  • stack খালি নয় এবং num < stack[-1] এবং attempts > 0 থাকা পর্যন্ত:

    • stack.pop()

    • attempts -= 1

  • stack.append(num)

• stack[:k] রিটার্ন করুন।

উদাহরণ

নিচের ইমপ্লিমেন্টেশনটি দেখুন:

def solve(nums, k):
    attempts = len(nums) - k
    stack = []
    for num in nums:
        while stack and num < stack[-1] and attempts > 0:
            stack.pop()
            attempts -= 1
        stack.append(num)
    return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

ইনপুট

[4,6,3,7], 2

আউটপুট

[3,7]