最大整除子集

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

给一个各不相同的正整数数组，挑出尽量多的数，要求任意两个都满足大的能被小的整除，返回一个最大子集（可跳着挑、不要求连续）。比如 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，最后只知子集多长，拼不回具体哪几个数。