最长公共递增子序列（Longest Common Increasing Subsequence）

我将为您详细讲解最长公共递增子序列（LCIS）问题。这是一个结合了最长公共子序列（LCS）和最长递增子序列（LIS）的经典动态规划问题。

问题描述

给定两个整数序列A和B，找到它们的最长公共子序列，且这个子序列必须是严格递增的。

示例：

• A = [1, 3, 2, 4]
• B = [3, 1, 2, 4]
• 最长公共递增子序列为 [1, 2, 4] 或 [3, 4]，长度都是3

解题思路

这个问题需要同时满足两个条件：

1. 是A和B的公共子序列
2. 子序列严格递增

我们将使用动态规划来解决这个问题。

动态规划解法

步骤1：定义状态

定义dp[j]表示：

• 以B[j]结尾的最长公共递增子序列的长度
• 且这个子序列同时是A[0..i]和B[0..j]的公共子序列

我们使用二维的思路，但通过优化可以简化为一维DP。

步骤2：状态转移方程

对于每个A[i]，我们遍历B的所有元素：

• 如果A[i] == B[j]：
  • 我们需要找到在B[0..j-1]中，所有B[k] < B[j]对应的dp[k]的最大值
  • 然后dp[j] = max_len + 1
• 如果A[i] != B[j]：
  • dp[j]保持不变（因为我们正在处理A的前i个元素）

步骤3：算法实现

def longest_common_increasing_subsequence(A, B):
    m, n = len(A), len(B)
    dp = [0] * n  # dp[j] 表示以B[j]结尾的LCIS长度
    
    for i in range(m):
        current_max = 0  # 记录当前满足B[k] < A[i]的最大dp值
        
        for j in range(n):
            if A[i] == B[j]:
                # 找到公共元素，更新dp[j]
                dp[j] = max(dp[j], current_max + 1)
            
            elif B[j] < A[i]:
                # 如果B[j] < A[i]，更新current_max
                current_max = max(current_max, dp[j])
    
    return max(dp) if dp else 0

步骤4：详细示例解析

让我们用示例A = [1, 3, 2, 4], B = [3, 1, 2, 4]来逐步分析：

初始化： dp = [0, 0, 0, 0]

处理A[0] = 1：

• j=0: B[0]=3 ≠ 1, 且3>1，不更新current_max
• j=1: B[1]=1 = 1, dp[1] = max(0, 0+1) = 1
• j=2: B[2]=2 > 1, 不更新
• j=3: B[3]=4 > 1, 不更新
  当前dp: [0, 1, 0, 0]

处理A[1] = 3：

• current_max = 0
• j=0: B[0]=3 = 3, dp[0] = max(0, 0+1) = 1
• j=1: B[1]=1 < 3, current_max = max(0, 1) = 1
• j=2: B[2]=2 < 3, current_max = max(1, 0) = 1
• j=3: B[3]=4 > 3, 不更新
  当前dp: [1, 1, 0, 0]

处理A[2] = 2：

• current_max = 0
• j=0: B[0]=3 > 2, 不更新
• j=1: B[1]=1 < 2, current_max = max(0, 1) = 1
• j=2: B[2]=2 = 2, dp[2] = max(0, 1+1) = 2
• j=3: B[3]=4 > 2, 不更新
  当前dp: [1, 1, 2, 0]

处理A[3] = 4：

• current_max = 0
• j=0: B[0]=3 < 4, current_max = max(0, 1) = 1
• j=1: B[1]=1 < 4, current_max = max(1, 1) = 1
• j=2: B[2]=2 < 4, current_max = max(1, 2) = 2
• j=3: B[3]=4 = 4, dp[3] = max(0, 2+1) = 3
  最终dp: [1, 1, 2, 3]

最大值为3，所以最长公共递增子序列长度为3。

步骤5：重构LCIS序列

如果需要输出具体的序列，我们可以修改算法来记录路径：

def longest_common_increasing_subsequence_with_path(A, B):
    m, n = len(A), len(B)
    dp = [0] * n
    prev = [-1] * n  # 记录前驱位置
    
    for i in range(m):
        current_max = 0
        last_index = -1
        
        for j in range(n):
            if A[i] == B[j]:
                if current_max + 1 > dp[j]:
                    dp[j] = current_max + 1
                    prev[j] = last_index
            elif B[j] < A[i]:
                if dp[j] > current_max:
                    current_max = dp[j]
                    last_index = j
    
    # 找到最大值和对应的索引
    max_len = 0
    max_index = -1
    for j in range(n):
        if dp[j] > max_len:
            max_len = dp[j]
            max_index = j
    
    # 重构序列
    result = []
    while max_index != -1:
        result.append(B[max_index])
        max_index = prev[max_index]
    
    return max_len, result[::-1]

复杂度分析

• 时间复杂度：O(m × n)，其中m和n分别是序列A和B的长度
• 空间复杂度：O(n)，使用了一维DP数组

总结

最长公共递增子序列问题通过巧妙地结合LCS和LIS的思路，使用动态规划高效解决。关键点在于：

1. 使用一维DP数组记录以每个位置结尾的LCIS长度
2. 在处理每个A[i]时，维护current_max来记录满足递增条件的最优解
3. 通过prev数组可以重构出具体的LCIS序列

这个算法在生物信息学、版本比较等领域有实际应用价值。