পাইথনে লংগেস্ট সার্কুলার ইনক্রিজিং সাবসিকোয়েন্সের দৈর্ঘ্য বের করার প্রোগ্রাম

ধরি আমাদের একটি নাম্বার লিস্ট nums আছে। আমাদের লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্সের দৈর্ঘ্য বের করতে হবে, যেখানে ধরা হচ্ছে সাবসিকোয়েন্স লিস্টের শুরুতে র‍্যাপ-আরাউন্ড হতে পারে।

তাই, ইনপুট যদি nums = [6, 5, 8, 2, 3, 4] হয়, তবে আউটপুট হবে ৫, কারণ লংগেস্ট ইনক্রিজিং সাবসিকোয়েন্স হলো [2, 3, 4, 6, 8]।

সমাধানের ধাপগুলো:

• a := numsর দ্বিগুণ আকারের লিস্ট তৈরি করে nums দুবার ফিল করুন
• ans := 0
• i = ০ থেকে len(nums) পর্যন্ত, করুন
  • dp := একটি নতুন লিস্ট
  • j = i থেকে len(nums) + i - 1 পর্যন্ত, করুন
    • n := a[j]
    • k := bisect_left(dp, n) (dp-তে n ইনসার্ট করার লেফটমোস্ট ইনডেক্স)
    • যদি k == len(dp), তবে
      • n কে dp-এর শেষে ইনসার্ট করুন
    • অন্যথায়,
      • dp[k] := n
    • ans := max(ans, len(dp))
• ans রিটার্ন করুন

বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

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