在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
- 对于i in range 1 to n,进行操作:
- 对于j in range 0 to i,进行操作:
- 如果nums [i]可以被nums [j]整除,则
- dp [i]:dp [i]和dp [j] +1的最大值
- ans:ans和dp [i]的最大值
- 对于j in range 0 to i,进行操作:
- 返回ans
更多Python相关文章,请阅读:Python 教程
示例(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