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

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যাকে nums বলা হয়, আমাদের দীর্ঘতম ক্রমবর্ধমান অনুক্রমের দৈর্ঘ্য খুঁজে বের করতে হবে এবং আমরা অনুমান করছি যে পরবর্তীটি তালিকার শুরুতে মোড়ানো হতে পারে।

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

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

• a :=সংখ্যার দুইবার আকারের একটি তালিকা তৈরি করুন এবং সংখ্যা দুইবার পূরণ করুন
• উত্তর :=0
• আমি 0 থেকে সংখ্যার আকারের মধ্যে,
  করুন
  • dp :=একটি নতুন তালিকা
  • j-এর জন্য রেঞ্জ i থেকে nums + i - 1, do
    • n :=a[j]
    • k :=dp-এ n ঢোকানোর জন্য সবচেয়ে বাম সূচক
    • যদি k dp এর আকারের সমান হয়, তাহলে
      • dp-এর শেষে n ঢোকান
    • অন্যথায়,
      • dp[k] :=n
    • উত্তর :=উত্তরের সর্বোচ্চ এবং ডিপির আকার
• উত্তর ফেরত দিন

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

উদাহরণ

import bisect
class Solution:
   def solve(self, nums):
      a = nums + nums
      ans = 0
      for i in range(len(nums)):
         dp = []
         for j in range(i, len(nums) + i):
            n = a[j]
            k = bisect.bisect_left(dp, n)
            if k == len(dp):
               dp.append(n)
            else:
               dp[k] = n
         ans = max(ans, len(dp))
      return ans

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

ইনপুট

[4, 5, 8, 2, 3, 4]

আউটপুট

5