পাইথনে দীর্ঘতম ক্রমবর্ধমান অনুক্রম

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

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

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

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

উদাহরণ

class Solution(object):
   def lengthOfLIS(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)
               #print(tails)
      return size
ob1 = Solution()
print(ob1.lengthOfLIS([10,9,2,5,3,7,101,18]))

ইনপুট

[10,9,2,5,3,7,101,18]

আউটপুট

4