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

更新于： 2020年12月12日

284 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告