去年离职的一位同事，今天突然出现在公司，他和大家打招呼，嘴上说“我又回来上班了”，同事们一个个面无表情，没有回应。

我在网上看到一个帖子。说是去年离职的一位同事，今天突然又出现在公司，进门还挺自然，笑嘻嘻跟大家打招呼，嘴里来一句：“我又回来上班了。”结果没人接话，空气都快凝固了。

这事看着尴尬，其实太真实了。走的时候多潇洒啊，嫌公司这不行那不行，背影都透着“爷要去更大的世界看看”。结果才四个月，又兜兜转转回来了。网友们看完也忍不住吐槽：原来不是前公司真差，是外面的饭更难吃。

这时候公司要是愿意收，他能老老实实干，其实也挺实在。毕竟职场混到最后，面子这玩意儿，有时候真没工资条好使。

给你一个无重复的正整数数组，找出一个子集，要求子集里任意两个数，较大的那个都能被较小的整除。

比如：

int[] nums = {1, 2, 3};

结果可以是 [1,2]，也可以是 [1,3]。

再看一组：

int[] nums = {1, 2, 4, 8};

这组就很顺了，答案直接是 [1,2,4,8]。

但这题如果真按“选或不选”去暴力搜，分支会很多，而且判断一个集合是否合法也不便宜。实际做的时候，先把数组排个序，思路会清楚很多。

先看关键点：如果数组已经升序，那么当 nums[i] % nums[j] == 0 且 j < i 时，说明 nums[i] 可以接在 nums[j] 对应的整除链后面。这个味道其实就是 LIS，最长递增子序列那套动态规划，只不过“能不能接”从大小比较变成了整除关系。

核心状态可以这样定义：

dp[i] = 以 nums[i] 结尾的最大整除子集长度
prev[i] = 这个位置往前接的是谁，方便最后回溯答案

转移也不复杂，枚举 i 前面的每个 j：

if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
    dp[i] = dp[j] + 1;
    prev[i] = j;
}

这题真正有用的地方，不是公式多漂亮，而是你得把“结果集怎么还原”一起想明白。很多人 dp 能写出来，最后答案还原就开始乱。

我自己会直接把完整代码写成这样：

import java.util.*;

classSolution{
public List<Integer> largestDivisibleSubset(int[] nums){
        Arrays.sort(nums);

int n = nums.length;
int[] dp = newint[n];
int[] prev = newint[n];
        Arrays.fill(dp, 1);
        Arrays.fill(prev, -1);

int maxLen = 1;
int maxIdx = 0;

for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] != 0) {
continue;
                }
if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    prev[i] = j;
                }
            }
if (dp[i] > maxLen) {
                maxLen = dp[i];
                maxIdx = i;
            }
        }

        List<Integer> ans = new ArrayList<>();
for (int i = maxIdx; i != -1; i = prev[i]) {
            ans.add(nums[i]);
        }
        Collections.reverse(ans);
return ans;
    }
}

拿 nums = [1,2,3,4,8] 走一下会更直观点。

排序后还是 [1,2,3,4,8]。

到 2 的时候，能接 1，所以链长变成 2。 到 3 的时候，也只能接 1，链长还是 2。 到 4 的时候，可以接 1，也可以接 2，显然接 2 更长。 到 8 的时候，又能接 1、2、4，这里接 4 最合适，最后得到 [1,2,4,8]。

中间状态大概长这样：

nums : [1, 2, 3, 4, 8]
dp   : [1, 2, 2, 3, 4]
prev : [-1, 0, 0, 1, 3]

最后从 maxIdx = 4 往前追：

8 -> 4 -> 2 -> 1

再反转一下，就是答案。

这题还有个容易写错的小地方：题目要求的是“任意一组最大子集”即可，不要求字典序最小，也不要求把所有答案都列出来。所以我们只要保住最长长度，再能把其中一条链回溯出来就够了，没必要把问题做复杂。

时间复杂度是 O(n^2)，空间复杂度 O(n)。 这个复杂度在这题里是够用的，别一看到双层循环就想着硬优化。因为它本质上要判断两两之间是否存在整除关系，这一步很难像普通 LIS 那样用二分去替掉。

顺手再给个测试片段，自己本地跑也方便：

publicstaticvoidmain(String[] args){
    Solution s = new Solution();
    System.out.println(s.largestDivisibleSubset(newint[]{1, 2, 3}));
    System.out.println(s.largestDivisibleSubset(newint[]{1, 2, 4, 8}));
    System.out.println(s.largestDivisibleSubset(newint[]{3, 4, 16, 8}));
}

输出类似这样：

[1, 2]
[1, 2, 4, 8]
[4, 8, 16]

这题做完以后，脑子里最好留一个印象： 只要题目里出现“先排序，再判断当前元素能不能接到前面的某个状态后面”，大概率就可以往 DP 链式转移上想。