सबसे बड़े उपसमुच्चय की लंबाई ज्ञात करने का कार्यक्रम जहां प्रत्येक जोड़ी में एक तत्व पायथन में दूसरे से विभाज्य है

मान लीजिए कि हमारे पास अंक नामक अद्वितीय संख्याओं की एक सूची है, इसलिए हमें सबसे बड़ा उपसमुच्चय खोजना होगा जैसे कि (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 की श्रेणी में i के लिए, करें
  • जे के लिए 0 से i की सीमा में, करें
    • यदि nums[i], nums[j] से विभाज्य है, तो
      • dp[i] :=अधिकतम dp[i] और dp[j] + 1
  • उत्तर:=अधिकतम उत्तर और डीपी[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