题解

思路

从左到右处理数组。对每个数值 $x$，只需知道当前已经出现的、以 $x$ 结尾的最长合法子序列。处理 $a_i=x$ 时，前一个值必须恰好为 $x-1$，因此把以 $x-1$ 结尾的最优方案接上位置 $i$ 即可。

做法

用哈希表维护：

• bestLength[x]：已处理前缀中，以值 $x$ 结尾的最大长度；
• bestIndex[x]：取得该长度时的最后一个下标。

对位置 $i$、值 $x=a_i$，令

同时令 parent[i]=bestIndex[x-1]。如果 $dp_i$ 优于当前的 bestLength[x]，就更新值 $x$ 的状态。记录全局最大状态，最后沿 parent 倒推并反转下标序列。

正确性证明

按处理位置归纳。考虑任意以位置 $i$ 结尾的合法子序列。若其长度大于 $1$，倒数第二个值必须是 $a_i-1$，并且倒数第二个下标小于 $i$。归纳假设保证哈希表已经保存所有此前位置中以 $a_i-1$ 结尾的最大长度，因此把位置 $i$ 接到该方案后得到以 $i$ 结尾的最优解，长度为 $bestLength[a_i-1]+1$。反之，这个转移连接的下标递增且数值恰好增加 $1$，所以必定合法。

对每个值只保留最大长度不会损失未来答案，因为未来只关心前驱值和长度；较短的同值结尾不可能比更长者带来更优扩展。于是全局最大状态就是答案，父指针恢复出的下标序列也满足全部要求。

复杂度分析

哈希表期望时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。