1.题目

给你一个由 无重复 正整数组成的集合 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 中的所有整数互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/largest-divisible-subset

2.思路

（1）动态规划
思路参考该 LeetCode 用户题解。

3.代码实现（Java）

//思路1————动态规划
class Solution {
    public static List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();
        Arrays.sort(nums);
        int length = nums.length;
        // f[i] 表示数组 nums 中以第 i 个数结尾的最长整除子集的长度
        int[] f = new int[length];
        // g[i] 记录 f[i] 是由哪个下标的状态转移而来，如果 f[i] = f[j] + 1, 则有 g[i] = j
        int[] g = new int[length];
        for (int i = 0; i < length; i++) {
            int len = 1, prev = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (f[j] + 1 > len) {
                        len = f[j] + 1;
                        prev = j;
                    }
                }
            }
            //记录最终长度和从何转移而来
            f[i] = len;
            g[i] = prev;
        }
        //遍历所有的 f[i]，取得最大长度和对应下标
        int max = -1, idx = -1;
        for (int i = 0; i < length; i++) {
            if (f[i] > max) {
                idx = i;
                max = f[i];
            }
        }
        //使用数组 g 回溯出具体方案
        while (res.size() != max) {
            res.add(nums[idx]);
            idx = g[idx];
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40