最近在给一位客户做 Google 面试实时辅助时，遇到了一道很典型的“subsequence + DP”问题，题目不难，但优化空间非常大。我们是如何快速从暴力走到最优解的？👇

💬 题目要求（原文）

Write a function which, given an array of integers, returns the length of the longest subsequence where every next value is 1 bigger than the previous one.
Subsequence might not be consecutive, but must be in the same order.

🧪 示例：

Input:  2 1 3 2 4 3 2 5 4 5
Output: 5
解释：最长合法子序列为：1 → 2 → 3 → 4 → 5

🧠 面试思路复盘

我们一开始澄清几个问题：

✅ 空数组 → 返回 0
✅ 所有元素一样 → 返回 1
✅ 子序列不是连续子数组，但顺序要保持 ✅

🚧 Step1 暴力思路（不建议）

暴力枚举所有子序列然后判断是否合法，时间复杂度高到离谱 O(2^n)，无法接受。

⚙️ Step2 动态规划解法一（O(n)）

我们使用哈希表 dp[num] = 最长以 num 结尾的子序列长度。

核心逻辑：

java复制编辑dp[num] = dp.get(num - 1, 0) + 1;

实时更新全局 maxLength，最终输出它。

Map<Integer, Integer> dp = new HashMap<>();
int maxLength = 0;
for (int num : nums) {
    int prevLength = dp.getOrDefault(num - 1, 0);
    dp.put(num, prevLength + 1);
    maxLength = Math.max(maxLength, dp.get(num));
}

⏱ Time: O(n)
📦 Space: O(n)

✅ 客户现场一次过，面试官点头✅

🔍 Step3 拓展思路：改为“差值 ≤ D”版

面试官 follow-up：

如果差值不是 1，而是允许最多差 D 呢？

我们升级为泛化版，用 HashMap 存储 num → 最长长度，同时考虑 num-1, num-2, ..., num-D 作为可能前缀。

for (int d = 1; d <= D; d++) {
    int prev = num - d;
    best = Math.max(best, dpMap.getOrDefault(prev, 0));
}
dpMap.put(num, best + 1);

⏱ 时间复杂度：O(n * D)（如果 D 较小，依然很快）
📦 空间复杂度：O(n)

🎯 最终优化：还原子序列路径

最后我们帮客户添加了 prev[i] 指针来恢复最长路径：

int[] dp = new int[n];
int[] prev = new int[n];

面试官进一步追问：

你能把最长的子序列完整打印出来吗？

我们引导客户讲出了完整 trace-back 思路，并恢复出正确路径（如 [1,2,3,4,5] 的索引序列）。

✅ 实战结果

整场面试中，客户：

• 思路清晰
• 代码一次过
• follow-up 拓展也答得非常顺畅

最终获得“Strong Hire”推荐！

🎓 面试启示

• 子序列类题建议先想：是否可以转换为“以 x 结尾”的状态？（用 dp 辅助）
• follow-up 若改条件如差值范围 / 重建路径，提前想好变量结构
• 真正顶级大厂看的是：你写完能不能讲清楚，能不能优化，能不能推演！

📮 如果你有 upcoming 的 Google / Meta / Amazon 面试，别孤军奋战。我们在面试中为你同步编写、推思路、补 follow-up，让你专注表达，稳定发挥。

欢迎私信咨询 面试辅助服务 ✅

不管你面对 Booking、Amazon、Meta 还是 TikTok，我们都能在面试过程中实时支持，确保你顺利答完题、讲清楚、留下好印象。

一场面试可能决定你能不能留下。我们会帮你，写好每一行代码，稳住每一个环节。