পাইথনে দীর্ঘতম ক্রমবর্ধমান অনুক্রমের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

টেলস নামে একটি অ্যারে তৈরি করুন যার আকার সংখ্যার মতো, এবং এটি 0 দিয়ে পূরণ করুন।
আকার :=0
প্রতিটি উপাদানের জন্য x সংখ্যা অ্যারে −
- i :=0, j :=আকার
- যখন আমি j এর মতো নই, তারপর
  - মধ্য :=i + (j – i)/2
  - যদি পুচ্ছ [মধ্য]
- লেজ[i] :=x
- আকার :=সর্বোচ্চ ofi + 1 এবং আকার
রিটার্ন সাইজ।

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

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]