最长公共递增子序列（LCIS）

我将详细讲解最长公共递增子序列（Longest Common Increasing Subsequence, LCIS）问题。这个问题结合了最长公共子序列（LCS）和最长递增子序列（LIS）的特点，要求找到两个序列中公共的且严格递增的子序列中最长的一个。

题目描述
给定两个整数序列A和B，找到最长的序列C，使得C既是A和B的公共子序列，又是严格递增的序列。例如：

• A = [1, 3, 5, 2, 8]
• B = [3, 2, 6, 1, 5, 8]
  一个LCIS是[3, 5, 8]，长度为3。另一个是[1, 5, 8]，长度也是3。最长的就是3。

解题过程

步骤1：理解问题本质
LCIS需要同时满足两个条件：

1. 公共性：子序列必须同时出现在A和B中（顺序一致，但可以不连续）
2. 递增性：子序列必须是严格递增的

步骤2：基础思路分析
最直接的方法是：

1. 找出A和B的所有公共子序列
2. 从中筛选出递增的子序列
3. 选择最长的
   但这种方法时间复杂度是指数级的，不可行。

步骤3：动态规划状态定义
我们定义dp[i][j]为：
以B[j]结尾的，考虑A的前i个元素和B的前j个元素时的最长公共递增子序列的长度。

关键点：我们固定子序列以B[j]结尾，这样便于处理递增性。

步骤4：状态转移方程推导
对于每个位置(i, j)，我们需要考虑两种情况：

情况1：A[i] ≠ B[j]
此时B[j]不能作为公共子序列的结尾与A[i]匹配，所以：
dp[i][j] = dp[i-1][j] （不考虑A[i]）

情况2：A[i] = B[j]
此时A[i]和B[j]匹配，可以作为一个公共元素。我们需要在前面找到一个更小的元素来维持递增性：
dp[i][j] = 1 + max{ dp[i-1][k] | 0 ≤ k < j 且 B[k] < B[j] }

解释：我们在B的前j-1个元素中，找到所有值小于B[j]的位置k，取其中dp[i-1][k]的最大值，然后加1（加上当前的B[j]）。

步骤5：算法实现细节
为了高效计算，我们可以：

1. 维护一个变量max_val，记录当前满足B[k] < B[j]的最大dp值
2. 当i固定时，随着j的增加，实时更新max_val

伪代码：

初始化dp为全0的m×n矩阵
for i = 1 to m:  // 遍历A的每个元素
    max_val = 0  // 记录当前最大的满足B[k] < B[j]的dp值
    for j = 1 to n:  // 遍历B的每个元素
        if A[i] != B[j]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max_val + 1
        
        // 更新max_val：只有当B[j] < A[i]时才更新
        // 因为下次遇到A[i] = B[j']时，需要B[j] < B[j'] = A[i]
        if B[j] < A[i]:
            max_val = max(max_val, dp[i-1][j])

步骤6：时间复杂度优化
上述算法的时间复杂度是O(mn)，空间复杂度可以通过滚动数组优化到O(n)。

步骤7：完整示例演示
以A = [1, 3, 5, 2, 8], B = [3, 2, 6, 1, 5, 8]为例：

初始化dp为5×6的全0矩阵

i=1 (A[1]=1):

• j=1: B[1]=3≠1, dp=0
• j=2: B[2]=2≠1, dp=0
• j=3: B[3]=6≠1, dp=0
• j=4: A[1]=B[4]=1, max_val=0 → dp=1
• j=5: B[5]=5≠1, dp=0
• j=6: B[6]=8≠1, dp=0

i=2 (A[2]=3):

• max_val初始=0
• j=1: A[2]=B[1]=3, dp=0+1=1
• j=2: B[2]=2<3, 更新max_val=max(0, dp[1][2]=0)=0
• j=3: B[3]=6≠3, dp=dp[1][3]=0
• j=4: B[4]=1<3, 更新max_val=max(0, dp[1][4]=1)=1
• j=5: A[2]=3≠5, dp=dp[1][5]=0
• j=6: B[6]=8≠3, dp=dp[1][6]=0

继续这个过程，最终找到最大值为3。

步骤8：结果提取
最终结果是所有dp[i][j]中的最大值，可以通过在计算过程中记录来获得。

这个算法优雅地结合了LCS和LIS的思想，通过巧妙的状态定义和递推关系，在O(mn)时间内解决了问题。