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
• 對列表 nums 進行排序
• n := nums 的大小
• 如果 n <= 1，則
  • 返回 n
• ans := 0
• 對於範圍從 1 到 n 的 i，執行以下操作：
  • 對於範圍從 0 到 i 的 j，執行以下操作：
    • 如果 nums[i] 可以被 nums[j] 整除，則
      • dp[i] := dp[i] 和 dp[j] + 1 的最大值
  • ans := ans 和 dp[i] 的最大值
• 返回 ans

示例（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

Arnab Chakraborty

更新於： 2020年12月12日

284 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習