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

题目描述：
给定两个整数数组A和B，找出它们的最长公共子序列，且这个子序列必须是严格递增的。返回这个子序列的长度。

示例：
输入：A = [1, 3, 5, 7, 9], B = [1, 4, 3, 5, 7, 8]
输出：4
解释：最长公共递增子序列是[1, 3, 5, 7]，长度为4

解题过程：

1. 问题分析：
   我们需要找到同时满足两个条件的子序列：

• 是A和B的公共子序列
• 是严格递增的

这可以看作是LCS（最长公共子序列）和LIS（最长递增子序列）的结合。

2. 基础思路：
   最直接的方法是先找出所有公共子序列，然后检查哪些是递增的，但这样时间复杂度太高（O(2^n)）。

我们可以用动态规划来优化：

• 定义dp[i][j]：以A[i]和B[j]结尾的最长公共递增子序列的长度
• 但这样定义有个问题：我们需要确保A[i] = B[j]，且子序列是递增的

3. 优化思路：
   我们采用更巧妙的定义：

• 定义dp[j]：以B[j]结尾的最长公共递增子序列的长度
• 遍历A数组，对于每个A[i]，我们更新dp数组

4. 具体算法步骤：

def lengthOfLCIS(A, B):
    if not A or not B:
        return 0
    
    m, n = len(A), len(B)
    dp = [0] * (n + 1)  # dp[j]表示以B[j-1]结尾的LCIS长度
    max_len = 0
    
    for i in range(m):
        current = 0  # 记录当前以小于A[i]的值结尾的LCIS的最大长度
        
        for j in range(n):
            if A[i] == B[j]:
                # 如果A[i]等于B[j]，可以扩展之前的LCIS
                dp[j] = current + 1
                max_len = max(max_len, dp[j])
            elif A[i] > B[j]:
                # 如果A[i]大于B[j]，更新current为以B[j]结尾的LCIS长度
                current = max(current, dp[j])
    
    return max_len

5. 详细解释：

• 外层循环遍历A的每个元素A[i]
• 内层循环遍历B的每个元素B[j]
• current变量记录：在当前A[i]之前，所有小于A[i]的B[j]对应的最长LCIS长度
• 当A[i] == B[j]时：我们可以用current + 1来更新dp[j]
• 当A[i] > B[j]时：B[j]可能成为未来某个LCIS的中间元素，所以更新current

6. 示例推演：
   A = [1, 3, 5, 7, 9], B = [1, 4, 3, 5, 7, 8]

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

• j=0: A[0]=B[0]=1, current=0 → dp[0]=1
• j=1: A[0]>B[1]=4? 不，1<4，不更新current
• j=2: A[0]>B[2]=3? 不，1<3，不更新current
  ...

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

• j=0: A[1]>B[0]=1 → current=max(0,dp[0]=1)=1
• j=1: A[1]<B[1]=4，不处理
• j=2: A[1]=B[2]=3 → dp[2]=current+1=2
  ...

7. 时间复杂度：O(m×n)
   空间复杂度：O(n)

这种方法巧妙地结合了LCS和LIS的思想，通过维护current变量来保证递增性。