最长公共上升子序列（LCIS）详细课堂笔记

---

一、题目概述

1. 题目描述

给定两个长度均为 $N$ 的数列 $A$ 和 $B$，求它们的**最长公共上升子序列（LCIS）**的长度。

• 公共子序列：同时是两个数列的子序列（元素位置不一定连续）。
• 上升子序列：数值严格递增的序列。

2. 输入输出格式

• 输入： 第一行：整数 $N$（数列长度）。 第二行：$N$ 个整数，表示数列 $A$。 第三行：$N$ 个整数，表示数列 $B$。
• 输出： 一个整数，表示 LCIS 的长度。

3. 样例分析

样例输入

4
2 2 1 3
2 1 2 3

样例输出

2

样例解释

满足条件的 LCIS 可以是 [2, 3] 或 [1, 3]，长度均为 2。

---

二、核心概念回顾

这道题是 最长上升子序列（LIS） 和 最长公共子序列（LCS） 的结合版，我们先复习这两个基础算法：

1. 最长上升子序列（LIS）

• 状态定义：f[i] 表示以第 i 个元素结尾的 LIS 长度。
• 状态转移：f[i] = max(f[j] + 1)（其中 j < i 且 a[j] < a[i]）。

2. 最长公共子序列（LCS）

• 状态定义：f[i][j] 表示 a[1~i] 和 b[1~j] 的 LCS 长度。
• 状态转移：
  • 若 a[i] == b[j]，则 f[i][j] = f[i-1][j-1] + 1；
  • 否则，f[i][j] = max(f[i-1][j], f[i][j-1])。

---

三、LCIS 算法思路详解

1. 状态定义（关键！）

我们融合 LIS 和 LCS 的状态定义：

• f[i][j]：表示在 a[1~i] 和 b[1~j] 中，以 b[j] 结尾的最长公共上升子序列的长度。

为什么以 b[j] 结尾？

因为上升子序列需要知道“最后一个元素的值”才能比较大小，方便后续状态转移（类似 LIS 的状态定义）。

2. 状态计算（集合划分思想）

我们将 f[i][j] 对应的集合划分成不重不漏的两部分：

情况 1：公共子序列不包含 a[i]

此时问题等价于“在 a[1~i-1] 和 b[1~j] 中以 b[j] 结尾的 LCIS”，因此：

f[i][j] = f[i-1][j]

情况 2：公共子序列包含 a[i]

此时必须满足两个条件：

1. a[i] == b[j]（因为是公共子序列，且以 b[j] 结尾，所以 a[i] 必须等于 b[j]）；
2. 子序列的倒数第二个元素必须小于 b[j]（因为是上升子序列）。

我们继续细分这部分：

• 子序列只包含 b[j] 一个数：长度为 1；
• 子序列倒数第二个元素是 b[1]：长度为 f[i-1][1] + 1；
• 子序列倒数第二个元素是 b[2]：长度为 f[i-1][2] + 1；
• ……
• 子序列倒数第二个元素是 b[j-1]：长度为 f[i-1][j-1] + 1。

因此，当 a[i] == b[j] 时：

f[i][j] = max{ f[i-1][k] + 1 | 0 ≤ k < j 且 b[k] < b[j] }

（注：k=0 表示子序列只有 b[j] 一个数，此时 f[i-1][0] = 0，长度为 1）

---

四、算法优化（从三重循环到两重循环）

1. 原始三重循环代码

如果直接按上述思路实现，会写出三重循环：

for (int i = 1; i <= n; i ++ )
{
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j]; // 情况1：不包含a[i]
        if (a[i] == b[j])
        {
            int maxv = 1; // 至少包含b[j]自己，长度为1
            for (int k = 1; k < j; k ++ ) // 找所有b[k] < b[j]的f[i-1][k]+1的最大值
                if (b[k] < b[j])
                    maxv = max(maxv, f[i - 1][k] + 1);
            f[i][j] = max(f[i][j], maxv);
        }
    }
}

• 时间复杂度：$O(n^3)$，当 $n=3000$ 时会超时！

2. 优化思路：维护前缀最大值

观察发现：当 i 固定时，j 从 1 到 n 遍历，我们可以实时维护一个变量 maxv，记录当前满足 b[k] < a[i] 的 f[i-1][k] + 1 的最大值。

为什么可以这样优化？

因为当 i 固定时，a[i] 是固定的，而 b[j] 是依次遍历的：

• 如果 a[i] > b[j]，说明 b[j] 可以作为后面某个 b[k]（k > j 且 b[k] = a[i]）的前驱，此时更新 maxv；
• 如果 a[i] == b[j]，直接用当前的 maxv 更新 f[i][j]（因为 maxv 已经记录了前面所有满足条件的最大值）。

3. 优化后的两重循环逻辑

for (int i = 1; i <= n; i ++ )
{
    int maxv = 1; // 维护当前满足a[i] > b[k]的f[i-1][k]+1的最大值
    for (int j = 1; j <= n; j ++ )
    {
        f[i][j] = f[i - 1][j]; // 情况1：不包含a[i]
        if (a[i] == b[j])
            f[i][j] = max(f[i][j], maxv); // 情况2：包含a[i]，用maxv更新
        if (a[i] > b[j])
            maxv = max(maxv, f[i - 1][j] + 1); // 更新maxv，为后面的j做准备
    }
}

• 时间复杂度：$O(n^2)$，完美通过 $n=3000$ 的数据！

---

五、代码实现

---

六、总结与关键点回顾

1. 核心技巧

• 状态定义：融合 LCS（两个序列）和 LIS（以某个元素结尾）的特点，方便转移。
• 优化思想：通过维护前缀最大值，将三重循环降为两重循环，这是 DP 优化中常用的技巧（减少重复计算）。

2. 注意事项

• 数组下标从 1 开始，避免处理 i=0 或 j=0 的边界问题。
• 最终答案要枚举 f[n][1~n] 的最大值，因为 LCIS 可以以 B 中任意元素结尾。