LeetCode 368. 最大整除子集题意给定一个无重复的正整数数组 nums找出其中最大的子集 answer使得 answer 中任意两个数都满足 answer[i] % answer[j] 0 或 answer[j] % answer[i] 0。返回任意一个满足条件的最大子集。思路动态规划类似最长上升子序列关键性质若将子集按升序排列 a₁ ≤ a₂ ≤ … ≤ aₖ则只需保证每个数都能被前一个数整除即可整除具有传递性。即排序后问题转化为「最长的整除链」。定义· dp[i]以 nums[i] 结尾的最长整除子集的长度。· 转移若 nums[i] % nums[j] 0j i则 dp[i] max(dp[i], dp[j] 1)。记录路径用 prev[i] 记录 i 是由哪个 j 转移来的最后从最长的 i 回溯构造答案。importjava.util.*;classSolution{publicListIntegerlargestDivisibleSubset(int[]nums){intnnums.length;Arrays.sort(nums);// 升序排序int[]dpnewint[n];// dp[i]: 以 nums[i] 结尾的最长子集长度int[]prevnewint[n];// prev[i]: 前驱下标Arrays.fill(dp,1);Arrays.fill(prev,-1);intmaxLen0,maxIdx0;// 记录最优结尾for(inti0;in;i){for(intj0;ji;j){if(nums[i]%nums[j]0dp[j]1dp[i]){dp[i]dp[j]1;prev[i]j;}}if(dp[i]maxLen){maxLendp[i];maxIdxi;}}// 回溯构造结果ListIntegerresnewArrayList();intcurmaxIdx;while(cur!-1){res.add(nums[cur]);curprev[cur];}returnres;// 逆序输出也没关系题目不要求顺序}}复杂度分析维度 复杂度时间 O(n²) — 双重循环空间 O(n) — dp / prev 数组示例演示以 nums [1, 2, 4, 8] 为例排序后不变i nums[i] dp[i] prev[i] 说明0 1 1 -1 初始1 2 2 0 2%102 4 3 1 4%203 8 4 2 8%40从 maxIdx3 回溯[8, 4, 2, 1]即最大整除子集。易错点与注意必须先排序不排序则无法保证「后面的数能被前面的数整除」这条链式关系成立。dp 初始化全为 1每个元素自身至少构成一个长度 1 的子集。prev 初始化 -1表示没有前驱用于回溯终止条件。整除具有传递性所以只需看相邻两个的整除关系dp 转移就等价于「链式」检验。返回顺序无关题目接受任意顺序回溯得到的逆序结果直接返回即可。小结本质是在整除偏序关系上求最长链排序后用 LIS最长上升子序列式的 O(n²) DP 即可。这是面试中该题的标准解法。