虚报了薪资流水入职后，公司要把我开除，每月薪资10000不到 我说我每个月25000

我在网上看到个帖子，味儿一下就冲上来了：月薪不到1万，面试时一口气报成2万5，想着把报价抬到3万，结果刚入职就被HR拿着流水“当场验明正身”。

有网友说得挺直接：你这不是谈薪，是开盲盒，开出来还是自己吓自己。还有人补刀：公司翻脸是快，可你这数字也确实吹得有点离谱。

说实话，公司拿虚报薪资说事，确实不好看，昨天还喊你来，今天就让你走，职场变脸比需求改版还勤快。但站在现实里看，薪资流水这种东西，真不是靠嘴硬就能圆过去。想要2n也难，毕竟问题的引线，还是自己先点的。

算法题：最大整除子集

这题我第一次看到时，直觉是回溯。毕竟题目要的是一个“子集”，很容易往“选或者不选”上想。但真写起来会发现，回溯虽然能做，数据一大就开始慢。这个题真正顺手的解法，还是动态规划。

题目叫最大整除子集：给你一组互不相同的正整数，找出一个最大的子集，让子集里任意两个数，都满足一个能整除另一个。

先看一个例子，[1,2,3]，结果可以是 [1,2]，也可以是 [1,3]。因为 2 和 3 互相都整除不了，所以不能一起留在同一个合法子集里。

这题有个很关键的动作：先排序。 排完序之后，如果 nums[i] % nums[j] == 0，那就说明较大的 nums[i] 可以接在 nums[j] 后面。问题一下就变成了：以 nums[i] 结尾的最大整除子集长度是多少。

我一般会这么写：

deflargestDivisibleSubset(nums):
ifnot nums:
return []

    nums.sort()
    n = len(nums)

    dp = [1] * n          # dp[i] 表示以 nums[i] 结尾的最大长度
    prev = [-1] * n       # 记录路径，方便最后倒着还原答案

    best_len = 1
    best_idx = 0

for i in range(n):
for j in range(i):
if nums[i] % nums[j] == 0and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                prev[i] = j

if dp[i] > best_len:
            best_len = dp[i]
            best_idx = i

    ans = []
while best_idx != -1:
        ans.append(nums[best_idx])
        best_idx = prev[best_idx]

return ans[::-1]

代码不长，核心就两层循环。 外层枚举当前数 nums[i]，内层去找它前面哪些数能整除它。如果能整除，而且能让链更长，就更新 dp[i] 和前驱节点 prev[i]。

比如输入：

print(largestDivisibleSubset([1, 2, 4, 8]))

输出就是：

[1, 2, 4, 8]

再看一个稍微绕一点的：

print(largestDivisibleSubset([3, 4, 16, 8]))

排序后是 [3,4,8,16]，最终会得到：

[4, 8, 16]

这里有个细节挺重要： 题目要求的是“任意两个数”满足整除关系，为什么我们只判断相邻转移就够了？

因为排序后，如果有一条链：

a -> b -> c

并且满足：

b % a == 0
c % b == 0

那自然也有：

c % a == 0

整除关系在这里是能传下去的，所以只要前一段链合法，后面接上去还是合法。

这题的时间复杂度是 O(n^2)，空间复杂度 O(n)。 如果只是面试或者刷题，这个复杂度基本就够用了。别一开始就想着剪枝、回溯优化，那个方向很容易把自己写乱，最后代码又长又不好讲。

我自己做这题时，真正卡住的点不是动态规划本身，而是结果怎么还原。很多人 dp 长度能算对，但最后只能返回长度，拿不回那个子集。这里加一个 prev 数组就顺了，谁转移过来的，就把下标记下来，最后从最长链的尾巴一路往前倒。

完整测试一下：

cases = [
    [1, 2, 3],
    [1, 2, 4, 8],
    [3, 4, 16, 8],
    [5, 9, 18, 54, 108]
]

for arr in cases:
    print(arr, "->", largestDivisibleSubset(arr))

这题不算特别难，但很适合拿来练“排序 + DP + 路径还原”这一套。面试看你写到这里，思路基本就比较稳了。