বৃহত্তম উপসেটের দৈর্ঘ্য খুঁজে বের করার প্রোগ্রাম যেখানে প্রতিটি জোড়ার একটি উপাদান পাইথনে অন্যটি দ্বারা বিভাজ্য

ধরুন আমাদের কাছে সংখ্যা নামক অনন্য সংখ্যার একটি তালিকা আছে, তাই আমাদেরকে সবচেয়ে বড় উপসেট খুঁজে বের করতে হবে যাতে (i, j) উপসেটের প্রতিটি জোড়া উপাদান হয় i % j =0 বা j % i =0 সন্তুষ্ট করে। তাই আমরা এই উপসেটের আকার খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[3, 6, 12, 24, 26, 39], তাহলে আউটপুট হবে 4, কারণ বৃহত্তম বৈধ উপসেট হল [3, 6, 12, 24]।

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

• dp :=আকার সংখ্যার একটি তালিকা এবং 1 দিয়ে পূরণ করুন
• তালিকা সংখ্যা সাজান
• n :=সংখ্যার আকার
• যদি n <=1 হয়, তাহলে
  • রিটার্ন n
• উত্তর :=0
• 1 থেকে n রেঞ্জের জন্য,
  করুন 0 থেকে i রেঞ্জে j-এর জন্য
  • করুন
    • যদি nums[i] nums[j] দ্বারা বিভাজ্য হয়, তাহলে
      • dp[i] :=সর্বাধিক dp[i] এবং dp[j] + 1
  • উত্তর :=সর্বাধিক উত্তর এবং dp[i]
• উত্তর ফেরত দিন

উদাহরণ (পাইথন)

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

class Solution:
   def solve(self, nums):
      dp = [1] * len(nums)
      nums.sort()
      n = len(nums)
      if n <= 1:
         return n
      ans = 0
      for i in range(1, n):
         for j in range(0, i):
            if nums[i] % nums[j] == 0:
            dp[i] = max(dp[i], dp[j] + 1)
         ans = max(ans, dp[i])
      return ans
ob = Solution()
nums = [3, 6, 12, 24, 26, 39]
print(ob.solve(nums))

ইনপুট

[3, 6, 12, 24, 26, 39]

আউটপুট

4