程序查找最大子集的长度，其中每对中的一个元素在Python中可被其他元素整除

假设我们有一个称为nums的唯一数字列表，所以我们必须找到最大的子集，以使子集中的每一对元素(i,j)都满足i％j = 0或j％i = 0。必须找到该子集的大小。

因此，如果输入类似于nums = [3，6，12，24，26，39]，则输出将为4，因为最大的有效子集为[3，6，12，24]。

为了解决这个问题，我们将遵循以下步骤-

• dp：=大小数字列表，并用1填充

• 排序列表

• n：= nums的大小

• 如果n <= 1，则

• 返回n

• 回答：= 0

• 对于1到n范围内的i，执行

• 如果nums [i]被nums [j]整除，则

• dp [i]：= dp [i]和dp [j]的最大值+ 1

• 对于范围在0到i之间的j，执行

• 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