LC 368. 最大整除子集

题目描述

这是 LeetCode 上的 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：

1
2
3

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

输出：[1,2,4,8]

提示：

$1 <= nums.length <= 1000$
$1 <= nums[i] <= 2 \times 10^9$
nums 中的所有整数互不相同

基本分析

根据题意：对于符合要求的「整除子集」中的任意两个值，必然满足「较大数」是「较小数」的倍数。

数据范围是 $10^3$，我们不可能采取获取所有子集，再检查子集是否合法的爆搜解法。

通常「递归」做不了，我们就往「递推」方向去考虑。

由于存在「整除子集」中任意两个值必然存在倍数/约数关系的性质，我们自然会想到对 nums 进行排序，然后从集合 nums 中从大到小进行取数，每次取数只考虑当前决策的数是否与「整除子集」中的最后一个数成倍数关系即可。

这时候你可能会想枚举每个数作为「整除子集」的起点，然后从前往后遍历一遍，每次都将符合「与当前子集最后一个元素成倍数」关系的数加入答案。

举个🌰，假设有原数组 [1,2,4,8]，“或许”我们期望的决策过程是：

遍历到数字 1，此时「整除子集」为空，加到「整除子集」中；
遍历到数字 2，与「整除子集」的最后一个元素（1）成倍数关系，加到「整除子集」中；
遍历到数字 4，与「整除子集」的最后一个元素（2）成倍数关系，自然也与 2 之前的元素成倍数关系，加到「整除子集」中；
遍历到数字 8，与「整除子集」的最后一个元素（4）成倍数关系，自然也与 4 之前的元素成倍数关系，加到「整除子集」中。

但这样的做法只能够确保得到「合法解」，无法确保得到的是「最长整除子集」。

当时担心本题数据太弱，上述错误的解法也能够通过，所以还特意实现了一下，还好被卡住了（🤣

同时也得到这个反例：[9,18,54,90,108,180,360,540,720]，如果按照我们上述逻辑，我们得到的是 [9,18,54,108,540] 答案（长度为 5），但事实上存在更长的「整除子集」： [9,18,90,180,360,720]（长度为 6）。

其本质是因为同一个数的不同倍数之间不存在必然的「倍数/约数关系」，而只存在「具有公约数」的性质，这会导致我们「模拟解法」错过最优解。

比如上述 🌰，54 & 90 和 18 存在倍数关系，但两者本身不存在倍数关系。

因此当我们决策到某一个数 nums[i] 时（nums 已排好序），我们无法直接将 nums[i] 直接接在符合「约数关系」的、最靠近位置 i 的数后面，而是要检查位置 i 前面的所有符合「约数关系」的位置，找一个已经形成「整除子集」长度最大的数。

换句话说，当我们对 nums 排好序并从前往后处理时，在处理到 nums[i] 时，我们希望知道位置 i 之前的下标已经形成的「整除子集」长度是多少，然后从中选一个最长的「整除子集」，将 nums[i] 接在后面（前提是符合「倍数关系」）。

动态规划

基于上述分析，我们不难发现这其实是一个序列 DP 问题：某个状态的转移依赖于与前一个状态的关系。即 nums[i] 能否接在 nums[j] 后面，取决于是否满足 nums[i] % nums[j] == 0 条件。

可看做是「最长上升子序列」问题的变形题。

定义 $f[i]$ 为考虑前 i 个数字，且以第 i 个数为结尾的最长「整除子集」长度。

我们不失一般性的考虑任意位置 i，存在两种情况：

如果在 i 之前找不到符合条件 nums[i] % nums[j] == 0 的位置 j，那么 nums[i] 不能接在位置 i 之前的任何数的后面，只能自己独立作为「整除子集」的第一个数，此时状态转移方程为 $f[i] = 1$；
如果在 i 之前能够找到符合条件的位置 j，则取所有符合条件的 f[j] 的最大值，代表如果希望找到以 nums[i] 为结尾的最长「整除子集」，需要将 nums[i] 接到符合条件的最长的 nums[j] 后面，此时状态转移方程为 $f[i] = f[j] + 1$。

同时由于我们需要输出具体方案，需要额外使用 g[] 数组来记录每个状态是由哪个状态转移而来。

定义 $g[i]$ 为记录 $f[i]$ 是由哪个下标的状态转移而来，如果 $f[i] = f[j] + 1$, 则有 $g[i] = j$。

对于求方案数的题目，多开一个数组来记录状态从何转移而来是最常见的手段。

当我们求得所有的状态值之后，可以对 f[] 数组进行遍历，取得具体的最长「整除子集」长度和对应下标，然后使用 g[] 数组进行回溯，取得答案。

Java 代码：

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        for (int i = 0; i < n; i++) {
            // 至少包含自身一个数，因此起始长度为 1，由自身转移而来
            int len = 1, prev = i;
            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 < n; i++) {
            if (f[i] > max) {
                idx = i;
                max = f[i];
            }
        }
        // 使用 g[] 数组回溯出具体方案
        List<Integer> ans = new ArrayList<>();
        while (ans.size() != max) {
            ans.add(nums[idx]);
            idx = g[idx];
        }
        return ans;
    }
}

C++ 代码：

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> f(n, 0), g(n, 0);
        for (int i = 0; i < n; i++) {
            int len = 1, prev = i;
            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;
        }
        int max = -1, idx = -1;
        for (int i = 0; i < n; i++) {
            if (f[i] > max) {
                max = f[i];
                idx = i;
            }
        }
        vector<int> ans;
        while (ans.size() != max) {
            ans.push_back(nums[idx]);
            idx = g[idx];
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        f, g = [0] * n, [0] * n
        for i in range(n):
            lenv, prev = 1, i
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    if f[j] + 1 > lenv:
                        lenv, prev = f[j] + 1, j
            f[i], g[i] = lenv, prev
        maxv, idx = -1, -1
        for i in range(n):
            if f[i] > maxv:
                maxv, idx = f[i], i
        ans = []
        while len(ans) != maxv:
            ans.append(nums[idx])
            idx = g[idx]
        return ans

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$

证明

之所以上述解法能够成立，问题能够转化为「最长上升子序列（LIS）」问题进行求解，本质是利用了「全序关系」中的「可传递性」。

在 LIS 问题中，我们是利用了「关系运算符 $\geqslant$ 」的传递性，因此当我们某个数 a 能够接在 b 后面，只需要确保 $a \geqslant b$ 成立，即可确保 a 大于等于 b 之前的所有值。

那么同理，如果我们想要上述解法成立，我们还需要证明如下内容：

「倍数/约数关系」具有传递性
由于我们将 nums[i] 往某个数字后面接时（假设为 nums[j]），只检查了其与 nums[j] 的关系，并没有去检查 nums[i] 与 nums[j] 之前的数值是否具有「倍数/约数关系」。

换句话说，我们只确保了最终答案 [a1, a2, a3, ..., an] 相邻两数值之间具有「倍数/约数关系」，并不明确任意两值之间具有「倍数/约数关系」。

因此需要证得由 $a | b$ 和 $b | c$，可推导出 $a | c$ 的传递性：

由 $a | b$ 可得 $b = x \times a$
由 $b | c$ 可得 $c = y \times b$

最终有 $c = y \times b = y \times x \times a$，由于 $x$ 和 $y$ 都是整数，因此可得 $a | c$。

得证「倍数/约数关系」具有传递性。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.368 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

序列 DP

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 897. 递增顺序搜索树上一篇

LC 363. 矩形区域不超过 K 的最大数值和下一篇