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

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

সুতরাং, যদি ইনপুটটি nums =[12, 14, 16, 5, 7, 8] k =2 এর মত হয়, তাহলে আউটপুট হবে 3, কারণ কমপক্ষে 2টি বিজোড় মানের সাথে দীর্ঘতম ক্রমবর্ধমান অনুক্রম হল [5, 7, ৮]।

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

সেরা :=0
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, j, odd, নেওয়া হবে
যদি বিজোড়>=k হয়, তাহলে
- সর্বোত্তম :=সর্বোত্তম এবং নেওয়া সর্বোচ্চ
যদি j সংখ্যার আকারের সমান হয়, তাহলে
- ফেরত
যদি nums[j]> nums[i] হয়, তাহলে
- dp(j, j + 1, odd +(nums[j] AND 1) , নেওয়া + 1)
dp(i, j + 1, odd, নেওয়া)
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
আমি 0 থেকে সংখ্যার আকারের মধ্যে, কর
- dp(i, i + 1, nums[i] এবং 1, 1)
সেরা ফেরত দিন

উদাহরণ

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

class Solution:
def solve(self, nums, k):
   best = 0
   def dp(i, j, odd, taken):
      nonlocal best
      if odd >= k:
         best = max(best, taken)
      if j == len(nums):
         return
      if nums[j] > nums[i]:
         dp(j, j + 1, odd + (nums[j] & 1), taken + 1)
      dp(i, j + 1, odd, taken)
   for i in range(len(nums)):
      dp(i, i + 1, nums[i] & 1, 1)
   return best
ob = Solution()
nums = [12, 14, 16, 5, 7, 8]
k = 2
print(ob.solve(nums, k))

ইনপুট

[12, 14, 16, 5, 7, 8], 2