Google VO 面试真题解析：最长连续递增 1 子序列（非连续）

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. The subsequence might not be consecutive, but must be in the same order as the given array.

Example:

Input:  2 1 3 2 4 3 2 5 4 5
Output: 5

这道题要求在给定整数数组中，找出一个按原顺序选取的最长子序列，使得子序列中相邻元素都恰好递增 1。核心做法通常是用动态规划配合哈希表：对每个数 x，记录以 x 结尾的最长合法子序列长度，并用 dp[x] = dp[x-1] + 1 进行转移。这样扫描一遍数组即可得到答案。题目示例中可以从 1、2、3、4、5 组成长度为 5 的序列，因此输出为 5。