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

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

问题描述

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

示例

• A = [1, 4, 2, 3, 5]
• B = [4, 1, 2, 3, 5]
• 最长公共递增子序列为 [1, 2, 3, 5] 或 [1, 2, 3, 5]（长度4）

解题思路

我们可以使用动态规划来解决这个问题。定义dp[i][j]表示以B[j]结尾的，且考虑A的前i个元素和B的前j个元素时的最长公共递增子序列的长度。

详细解题步骤

步骤1：状态定义
定义dp[i][j]：以B[j]结尾，且考虑A[1..i]和B[1..j]时的最长公共递增子序列长度。

步骤2：状态转移方程

对于每个位置(i, j)，我们需要考虑两种情况：

1. 如果A[i] ≠ B[j]

   • 那么B[j]不能作为公共递增子序列的结尾元素
   • dp[i][j] = dp[i-1][j]

2. 如果A[i] = B[j]

   • 那么我们需要在B[1..j-1]中找到一个位置p，使得B[p] < B[j]，并且dp[i-1][p]最大
   • dp[i][j] = max{dp[i-1][p]} + 1，其中1 ≤ p < j且B[p] < B[j]

步骤3：基础情况

• 当i = 0或j = 0时，dp[i][j] = 0（空序列）

步骤4：算法实现

我们可以优化状态转移过程，避免每次都重新扫描前面的所有位置：

def longest_common_increasing_subsequence(A, B):
    n, m = len(A), len(B)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        # 记录当前最大长度
        max_len = 0
        for j in range(1, m + 1):
            # 继承上一行的结果
            dp[i][j] = dp[i-1][j]
            
            if A[i-1] == B[j-1]:
                # 找到满足条件的最大长度
                dp[i][j] = max_len + 1
            elif A[i-1] > B[j-1]:
                # 更新max_len，为后面可能的匹配做准备
                max_len = max(max_len, dp[i-1][j])
    
    # 找到最大值
    result = 0
    for j in range(1, m + 1):
        result = max(result, dp[n][j])
    
    return result

步骤5：空间优化

我们可以将空间复杂度优化到O(m)：

def lcis_optimized(A, B):
    n, m = len(A), len(B)
    dp = [0] * (m + 1)  # 当前行的dp值
    
    for i in range(1, n + 1):
        max_len = 0
        for j in range(1, m + 1):
            if A[i-1] == B[j-1]:
                dp[j] = max_len + 1
            elif A[i-1] > B[j-1]:
                max_len = max(max_len, dp[j])
    
    return max(dp)

步骤6：重构LCIS

如果需要输出具体的子序列，我们可以记录路径信息：

def lcis_with_path(A, B):
    n, m = len(A), len(B)
    dp = [0] * (m + 1)
    prev = [-1] * (m + 1)  # 记录前驱位置
    
    for i in range(1, n + 1):
        max_len = 0
        best_prev = -1
        for j in range(1, m + 1):
            if A[i-1] == B[j-1]:
                dp[j] = max_len + 1
                prev[j] = best_prev
            elif A[i-1] > B[j-1]:
                if dp[j] > max_len:
                    max_len = dp[j]
                    best_prev = j
    
    # 找到最大值和结束位置
    max_len = 0
    end_pos = -1
    for j in range(1, m + 1):
        if dp[j] > max_len:
            max_len = dp[j]
            end_pos = j
    
    # 重构序列
    result = []
    pos = end_pos
    while pos != -1:
        result.append(B[pos-1])
        pos = prev[pos]
    
    return result[::-1]  # 反转得到正确顺序

时间复杂度分析

• 时间复杂度：O(n×m)
• 空间复杂度：O(m)（优化后）

示例验证

对于A = [1, 4, 2, 3, 5], B = [4, 1, 2, 3, 5]：

• 算法会找到LCIS为[1, 2, 3, 5]
• 长度为4

这个算法巧妙地结合了LCS和LIS的思想，通过动态规划高效地解决了问题。