最大整除子集 图解题解

最大整除子集到底在找什么

给一个各不相同的正整数数组，挑出尽量多的数，要求任意两个都满足大的能被小的整除，返回一个最大子集（可跳着挑、不要求连续）。比如 nums = [3,4,16,8] 的答案是 [4,8,16]。答案不唯一，返回任一最大的即可。

为什么不能把所有子集都试一遍

最直接是列出所有子集逐个检查是否两两整除，留最大的。但 n 个数有 2^n 个子集，n=30 就十亿量级，跑不完。

两两整除有结构可挖：数从小到大排好后，一个数只可能接在比它小、又能整除它的数后面。问题从「挑一堆数」变成「从左到右每个数往前找一条最长链」。

为什么要先排序，dp[i] 又代表什么

先把 nums 从小到大排序，排完后能整除某个数的因子一定在它左边，每个数只需往左看。

定义 dp[i] 为「以排序后第 i 个数结尾的最大整除子集有多长」，至少是 1（自己单独成子集）。算 dp[i] 就扫左边所有 j：只要 nums[i] % nums[j] == 0，nums[i] 就能接在以 j 结尾的链后面变成 dp[j] + 1，在能接的 j 里挑 dp[j] 最大的即为 dp[i]。这就是最长递增子序列（LIS，最长的逐个变大的子序列）的套路，只把「后一个更大」换成「后一个能被前一个整除」。

只验证相邻两数整除，为什么整个子集就都整除

链上只验证了相邻两数整除，隔着的两数凭什么也整除？靠整除的传递性——a 整除 b、b 整除 c，则 a 一定整除 c。相邻都整除一路传下去，任意两个也就都整除。

只算长度还不够，题目要的是具体子集，所以再开一个 parent 数组（parent[i] 记 nums[i] 前一个数的下标，即前驱指针），更新 dp[i] 时记下它接在谁后面。最后从 dp 最大处顺着 parent 往回跳，沿途的数就是整条链。

拿 [3,4,16,8] 亲手算一遍

拿题面 nums = [3,4,16,8] 走一遍：排序成 [3,4,8,16]，dp 全初始化为 1，parent 全是 -1。

3：左边没数，dp[0]=1。4：4 % 3 ≠ 0，dp[1]=1。8：8 % 4 == 0，接到 4，dp[2]=dp[1]+1=2，parent[2]=1。16：接 4 只到长度 2，接 8（16 % 8 == 0）能到 3，取更长，dp[3]=dp[2]+1=3，parent[3]=2。

四个 dp 值 [1,1,2,3]，最大 dp[3]=3。从下标 3（数 16）回溯：parent 依次指到 8、4，再到 -1 到头。收集到 16、8、4，倒过来是 [4,8,16]，正是答案。

复杂度是多少，不排序和不记 parent 会怎样

排序 O(n log n)；主体 i、j 两层循环、每对一次取模 O(1)，合起来 O(n²)，回溯 O(n)，整体 O(n²) 主导。空间上 dp、parent 各 O(n)。

两处最容易踩坑：一是不排序直接 DP，「因子在左边」的前提没了，顺序乱的整除关系会漏掉；二是只记 dp 长度、忘了 parent，最后只知子集多长，拼不回具体哪几个数。

Python

from typing import List
class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        best = 0
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
            if dp[i] > dp[best]:
                best = i
        ans = []
        while best != -1:
            ans.append(nums[best])
            best = parent[best]
        return ans

C++

#include <algorithm>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), best = 0;
        vector<int> dp(n, 1), parent(n, -1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1; parent[i] = j;
            }
            if (dp[i] > dp[best]) best = i;
        }
        vector<int> ans;
        while (best != -1) { ans.push_back(nums[best]); best = parent[best]; }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length, best = 0;
        int[] dp = new int[n], parent = new int[n];
        Arrays.fill(dp, 1); Arrays.fill(parent, -1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1; parent[i] = j;
            }
            if (dp[i] > dp[best]) best = i;
        }
        List<Integer> ans = new ArrayList<>();
        while (best != -1) { ans.add(nums[best]); best = parent[best]; }
        return ans;
    }
}