离职同事突现公司宣称回归，同事们却冷漠回应

我在网上看到个帖子，真有点职场连续剧那味儿了。

去年刚离职的一个同事，前脚走得那叫一个潇洒，架势像是马上要去更大的山头当大王。结果才过了四个月，今天人又出现在公司门口，进来还乐呵呵跟大家打招呼，来一句：“我又回来上班了。”空气当场安静，周围同事一张张脸比工位电脑待机界面还冷，愣是没人接话。

说真的，这事尴尬归尴尬，也挺真实。很多人离职时总觉得外面遍地机会，老板都像财神爷，去了才知道，饼更大，坑也更深。回来不丢人，装得若无其事才最考验脸皮。职场这地方，有时候真不是公司离不开你，是你出门一趟才知道，原来这班还算能上。

算法 题： 最大整除子集

这题我第一次刷到的时候，直觉会往回溯上想：枚举所有子集，再判断两两能不能整除。代码倒是不难写，但数据一大基本就没法看了。

“最大整除子集”这题更像最长递增子序列的变种，关键动作只有两个： 先排序，再做动态规划 。排完序之后，如果 nums[i] % nums[j] == 0 ，那就说明 nums[i] 可以接到 nums[j] 这个子集后面。

比如数组是：

int nums = {1, 2, 3, 4, 8, 9};

排序后还是它自己。看到 8 的时候，它能接在 1 -> 2 -> 4 后面，于是就形成更长的链。这个过程其实和 LIS 很像，只不过比较条件从大小关系，变成了整除关系。

我一般会准备两个数组：

int dp = newint[n]; // 以 nums[i] 结尾的最大子集长度
int prev = newint[n]; // 记录前驱节点，方便最后回溯答案
Arrays.fill(dp, 1);
Arrays.fill(prev, -1);

dp[i] = 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;
prev[i] = j;
}
}
}

这里不用想复杂。就是看 i 前面的每个数，谁能整除，谁就有资格接上；谁接上之后链更长，就选谁。

完整 java 写法我习惯这样写，够直接：

import java.util.*;

publicclassSolution{
public ListlargestDivisibleSubset(int[] nums){
List ans = new ArrayList<>;
if (nums == || nums.length == 0) {
return ans;
}

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 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (dp[i] > maxLen) {
maxLen = dp[i];
maxIdx = i;
}
}

while (maxIdx != -1) {
ans.add(nums[maxIdx]);
maxIdx = prev[maxIdx];
}

Collections.reverse(ans);
return ans;
}
}

这段代码里，前半部分是在算“最长能到哪”，后半部分是在“把路径捡回来”。

比如输入：

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

最后结果就是：

[1, 2, 4, 8]

如果输入是：

int nums = {1, 2, 3};

那结果可能是：

[1, 2]

或者：

[1, 3]

都对。因为题目只要求返回任意一个最大整除子集，不要求唯一。

这题有个容易忽略的小点： 为什么排序后就能放心做 DP？ 因为一旦排完序，后面的数只会更大。只要 nums[i] 能被 nums[j] 整除，那么从小到大接链不会乱，整条路径也更容易维护。不排序的话，状态之间的依赖关系就很散，代码会很拧巴。

时间复杂度是 O(n^2) ，空间复杂度是 O(n) 。这题在面试里不算特别难，但挺适合考察你是不是能把“回溯暴力”收一收，转成“排序 + DP + 路径还原”这套更稳的写法。

真写的时候，别急着上完整框架，先把这一句想清楚就行：

if (nums[i] % nums[j] == 0)

这个条件，就是整道题的转移入口。后面其实都是顺着它往下写。