โปรแกรมค้นหาความยาวของชุดย่อยที่ใหญ่ที่สุดโดยองค์ประกอบหนึ่งในทุกคู่หารด้วยองค์ประกอบอื่นในPython

สมมติว่าเรามีรายการตัวเลขที่ไม่ซ้ำกันซึ่งเรียกว่า nums ดังนั้นเราต้องหาชุดย่อยที่ใหญ่ที่สุดเพื่อให้องค์ประกอบทุกคู่ในเซตย่อย เช่น (i, j) เป็นไปตาม i % j =0 หรือ j % i =0 ดังนั้นเราจึง ต้องหาขนาดของเซตย่อยนี้

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[3, 6, 12, 24, 26, 39] เอาต์พุตจะเป็น 4 เนื่องจากเซตย่อยที่ถูกต้องที่สุดคือ [3, 6, 12, 24]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• dp :=รายการขนาด nums และเติม 1
• เรียงเลขรายการ
• n :=ขนาดของ nums
• ถ้า n <=1 แล้ว
  • ส่งคืน n
• ตอบ :=0
• สำหรับฉันในช่วง 1 ถึง n ทำ
  • สำหรับ j ในช่วง 0 ถึง i ทำ
    • ถ้า nums[i] หารด้วย nums[j] ลงตัว ดังนั้น
      • dp[i] :=สูงสุดของ dp[i] และ dp[j] + 1
  • ans :=สูงสุดของ ans และ dp[i]
• คืนสินค้า

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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