পাইথনে সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

ধরা যাক একটি সংখ্যার তালিকা আছে। আমাদের সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্সের দৈর্ঘ্য খুঁজে বের করতে হবে। উদাহরণস্বরূপ, ইনপুট [6, 1, 7, 2, 8, 3, 4, 5] হলে আউটপুট হবে 5, কারণ সর্বোচ্চ ক্রমবর্ধমান সাবসিকোয়েন্স হল [2, 3, 4, 5, 6]।

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

• tails নামক একটি অ্যারে তৈরি করুন যার আকার nums-এর সমান, এবং 0 দিয়ে ভরুন।

• size := 0

• nums-এর প্রতিটি উপাদান x-এর জন্য:

  • i := 0, j := size
  • যখন i ≠ j, তখন:
  • mid := i + (j - i) // 2
  • যদি tails[mid] < x হয়, তবে i := mid + 1, অন্যথায় j := mid
  • tails[i] := x
  • size := max(i + 1, size)

• size ফেরত দিন।

উদাহরণ কোড

class Solution(object):
    def solve(self, nums):
        tails = [0 for i in range(len(nums))]
        size = 0
        for x in nums:
            i = 0
            j = size
            while i != j:
                mid = i + (j - i) // 2
                if tails[mid] < x:
                    i = mid + 1
                else:
                    j = mid
            tails[i] = x
            size = max(i + 1, size)
        return size

ob = Solution()
nums = [7, 2, 8, 3, 9, 4, 5, 6]
print(ob.solve(nums))

ইনপুট

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

আউটপুট

5