0368：最大整除子集（★）

2016-01-03 约 325 字预计阅读 1 分钟次阅读

力扣第 368 题

题目

给你一个由 无重复 正整数组成的集合 nums ，请你找出并返回其中最大的整除子集 answer ，子集中每一元素对 (answer[i], answer[j]) 都应当满足：

answer[i] % answer[j] == 0 ，或
answer[j] % answer[i] == 0

如果存在多个有效解子集，返回其中任何一个均可。

示例 1：

输入：nums = [1,2,3]
输出：[1,2]
解释：[1,3] 也会被视为正确答案。

示例 2：

输入：nums = [1,2,4,8]
输出：[1,2,4,8]

提示：

1 <= nums.length <= 1000
1 <= nums[i] <= 2 * 10⁹
nums 中的所有整数 互不相同

分析

先将 nums 排序后得到数组 A
令 f[i] 代表以位置 i 结尾的最大长度，按前一个位置即可递推
要求一个具体的子集，在递推时保存最优情况下的前一个位置即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        A = sorted(nums)
        n = len(A)
        f = [1]*n
        g = [-1]*n
        for i in range(1,n):
            for j in range(i):
                if A[i]%A[j]==0 and 1+f[j]>f[i]:
                    f[i] = 1+f[j]
                    g[i] = j
        i = f.index(max(f))
        res = []
        while i>=0:
            res.append(A[i])
            i = g[i]
        return res

203 ms

目录

0368：最大整除子集（★）

题目

分析

解答