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

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

问题描述

给定两个整数数组nums1和nums2，请找出它们的最长公共递增子序列的长度。公共递增子序列需要满足：

1. 是nums1和nums2的公共子序列
2. 该子序列是严格递增的

示例：

nums1 = [1, 3, 5, 7, 9]
nums2 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
输出：5
解释：最长公共递增子序列是[1, 3, 5, 7, 9]，长度为5

解题思路

步骤1：理解问题本质

这个问题实际上是两个经典问题的结合：

• 最长公共子序列（LCS）：找到两个序列的公共子序列
• 最长递增子序列（LIS）：找到严格递增的子序列

我们需要同时满足这两个条件，找到既公共又递增的最长子序列。

步骤2：定义状态

我们定义动态规划数组：

• dp[j]：表示以nums2[j]结尾的最长公共递增子序列的长度

这里的关键洞察是：我们固定遍历nums1，对于nums1中的每个元素，我们遍历nums2来更新状态。

步骤3：状态转移方程

对于每个nums1[i]，我们遍历nums2：

1. 如果nums1[i] == nums2[j]，说明我们找到了一个公共元素
2. 我们需要找到在nums2中位置j之前，且值小于nums2[j]的所有位置，取其中的最大LCIS长度

具体算法：

def lengthOfLCIS(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * n  # dp[j]表示以nums2[j]结尾的LCIS长度
    
    for i in range(m):
        current_max = 0  # 记录当前满足递增条件的最长长度
        
        for j in range(n):
            if nums1[i] == nums2[j]:
                # 找到公共元素，更新dp[j]
                dp[j] = max(dp[j], current_max + 1)
            
            elif nums2[j] < nums1[i]:
                # 如果nums2[j] < nums1[i]，说明nums2[j]可能作为递增序列的前驱
                current_max = max(current_max, dp[j])
    
    return max(dp) if dp else 0

步骤4：详细算法解析

让我通过一个具体例子来详细解释：

示例：

nums1 = [1, 3, 2, 4]
nums2 = [1, 2, 3, 4]

执行过程：

i=0 (nums1[0]=1):

• j=0: nums2[0]=1 == nums1[0]=1 → dp[0] = max(0, 0+1) = 1
• j=1: nums2[1]=2 > 1 → current_max保持0
• j=2: nums2[2]=3 > 1 → current_max保持0
• j=3: nums2[3]=4 > 1 → current_max保持0
  dp = [1, 0, 0, 0]

i=1 (nums1[1]=3):

• current_max = 0
• j=0: nums2[0]=1 < 3 → current_max = max(0, dp[0]=1) = 1
• j=1: nums2[1]=2 < 3 → current_max = max(1, dp[1]=0) = 1
• j=2: nums2[2]=3 == 3 → dp[2] = max(0, 1+1) = 2
• j=3: nums2[3]=4 > 3 → 无操作
  dp = [1, 0, 2, 0]

i=2 (nums1[2]=2):

• current_max = 0
• j=0: nums2[0]=1 < 2 → current_max = max(0, dp[0]=1) = 1
• j=1: nums2[1]=2 == 2 → dp[1] = max(0, 1+1) = 2
• j=2: nums2[2]=3 > 2 → 无操作
• j=3: nums2[3]=4 > 2 → 无操作
  dp = [1, 2, 2, 0]

i=3 (nums1[3]=4):

• current_max = 0
• j=0: nums2[0]=1 < 4 → current_max = max(0, dp[0]=1) = 1
• j=1: nums2[1]=2 < 4 → current_max = max(1, dp[1]=2) = 2
• j=2: nums2[2]=3 < 4 → current_max = max(2, dp[2]=2) = 2
• j=3: nums2[3]=4 == 4 → dp[3] = max(0, 2+1) = 3
  dp = [1, 2, 2, 3]

最终结果：max(dp) = 3
最长公共递增子序列：[1, 2, 4] 或 [1, 3, 4]

步骤5：重构LCIS序列

如果我们还需要找出具体的LCIS序列，可以添加一个prev数组来记录前驱位置：

def findLCIS(nums1, nums2):
    m, n = len(nums1), len(nums2)
    dp = [0] * n
    prev = [-1] * n  # 记录前驱位置
    
    for i in range(m):
        current_max = 0
        last_index = -1  # 记录当前最大长度对应的索引
        
        for j in range(n):
            if nums1[i] == nums2[j]:
                if current_max + 1 > dp[j]:
                    dp[j] = current_max + 1
                    prev[j] = last_index
            
            elif nums2[j] < nums1[i]:
                if dp[j] > current_max:
                    current_max = dp[j]
                    last_index = j
    
    # 找到最大值的索引
    max_len = 0
    end_index = -1
    for j in range(n):
        if dp[j] > max_len:
            max_len = dp[j]
            end_index = j
    
    # 重构序列
    if end_index == -1:
        return []
    
    result = []
    while end_index != -1:
        result.append(nums2[end_index])
        end_index = prev[end_index]
    
    return result[::-1]  # 反转得到正确顺序

复杂度分析

• 时间复杂度：O(m×n)，其中m和n分别是两个数组的长度
• 空间复杂度：O(n)，我们只需要一个长度为n的dp数组

算法优化

对于某些特殊情况，我们可以进行优化：

1. 如果数组已经排序，可以利用二分查找优化
2. 如果数组范围较小，可以使用哈希表预处理

这个算法巧妙地结合了LCS和LIS的思想，通过维护current_max变量来确保递增性，是动态规划中状态压缩的经典应用。