题解

思路

公共递增子序列的最后一个元素一定等于第二个序列中的某个 $b_j$。围绕“以 $b_j$ 结尾的最优长度”设计状态，就能同时保证公共性、下标顺序和严格递增性。

做法

子任务 1 枚举第一个序列的全部子序列。只保留严格递增者，再用双指针检查它是否也是第二个序列的子序列，取最长者。

子任务 2 维护 $d_j$，表示处理过第一个序列的某个前缀后，以 $b_j$ 结尾的 LCIS 长度。遇到 $a_i=b_j$ 时，扫描全部 $q<j$ 且 $b_q<a_i$ 的状态转移，得到 $O(nm^2)$ 的直接动态规划；同时记录前驱下标以恢复方案。

满分算法在固定 $a_i$ 扫描 $b_1,\ldots,b_m$ 时维护变量 best：它是当前已经扫过且值小于 $a_i$ 的 $d_j$ 最大值，并保存对应下标。于是：

• 若 $b_j<a_i$，用 $d_j$ 更新 best；
• 若 $b_j=a_i$，用 best+1 更新 $d_j$，并把 best 的下标记录为前驱。

每一轮只需线性扫描第二个序列。最后找最大的 $d_j$，沿前驱链逆序恢复答案。

复杂度

子任务 1 的时间复杂度为 $O(2^n(n+m))$，空间复杂度为 $O(n)$。子任务 2 的时间复杂度为 $O(nm^2)$，空间复杂度为 $O(m)$。满分算法的时间复杂度为 $O(nm)$，空间复杂度为 $O(m)$。

正确性证明

对固定的 $a_i$ 从左到右扫描 $b$。变量 best 始终等于此前所有满足 $b_q<a_i$ 的合法结尾状态最大值，因此当 $a_i=b_j$ 时，best+1 恰好枚举了所有可接到该公共元素之前的 LCIS，并选出最长者。状态只从已经处理过的 $a$ 前缀和更小的、位置更靠前的 $b_q$ 转移，所以得到的序列同时满足两个子序列顺序且严格递增。归纳每个 $a_i$ 后所有 $d_j$ 均正确，最终最大状态就是 LCIS 长度，前驱链给出对应合法方案。