---
title: "最长公共上升子序列"
created: 2025-11-28
tags:
  - 算法
---

# 最长公共上升子序列

## 题目  [最长公共上升子序列](https://www.acwing.com/problem/content/description/274/)

![[image-e975ff7a.png]]

## 思路分析

这是两个**经典DP模型**的结合版：

LIS(最长上升子序列，Longest Increasing Subsequence)

`for(j=1;j<i;j++) if(a[j]<a[i]) f[i]=f[j]+1`

LCS(最长公共子序列，Longest Common Subsequence)

`f[i][j]=max({f[i][j-1],f[i-1][j],f[i-1][j-1]+(a[i]==b[j])})`

LCIS(最长公共上升子序列，Longest Common Increasing Subsequence)

LCIS 也是一个相当经典的DP模型，他的 状态分析 是 LIS 与 LCS 的结合

首先两个序列所以用f[i][j]来表示状态

不过现在的f[i][j]的含义有所变化——考虑 a 中前 i 个数字，b 中前 j 个数字 ，且当前以 b[j] 结尾的子序列的方案

（因为在公共子序列的基础上加了一个上升的限制 所以现在不能每个都选了 是否能选得根据上一个位置是什么决定 这个上一个位置就存在b[j]当中）

属性自然是max

状态转移

首先看a[i]位置可不可选 如果不可选的话状态应该是从f[i-1][j]转移过来

如果a[i]可选 还得看它到底从哪个位置转移过来 如果a[i-1]等于b[1]那么就应该从f[i-1][1]转移过来 同理 如果等于b[k]就得从f[i-1][k]转移过来

由此划分出两个不重不漏的子集

![[image-992e51ef.png]]

![[image-89c0b1e1.png]]

不包含a[i]的子集，最大值是f[i - 1][j]；

包含a[i]的子集，将这个子集继续划分，依据是子序列的倒数第二个元素在b[]中是哪个数：

子序列只包含b[j]一个数，长度是1；

子序列的倒数第二个数是b[1]的集合，最大长度是f[i - 1][1] + 1；

 …

子序列的倒数第二个数是b[j - 1]的集合，最大长度是f[i - 1][j - 1] + 1；

由此写出朴素做法：

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=3010;

int a[N],b[N];

int f[N][N];

int n;

int main()

{

    cin>>n;

    for(int i=1;i<=n;i++)

        cin>>a[i];

    for(int i=1;i<=n;i++)

        cin>>b[i];

    for(int i=1;i<=n;i++){

        for(int j=1;j<=n;j++){

            f[i][j]=f[i-1][j];

            if(a[i]==b[j]){

                for(int k=0;k<j;k++){

                    if(b[j]>b[k]){

                        f[i][j]=max(f[i][j],f[i-1][k]+1);

                    }

                }

            }

        }

    }

    int res=0;

    for(int i=0;i<=n;i++)

        res=max(res,f[n][i]);

    cout<<res;

    return 0;

}
```

tle了

![[image-5b3fd178.png]]

我们可以观察到，对于第二种状态转移：

$f\_{i,j}=max(f\_{i,j},f\_{i−1,k}+1)   k∈[0,j−1],a\_i=b\_j,b\_j>b\_k$

每次用到的 状态 都是第 i - 1 个阶段的

因此我们可以用一个变量，存储上一个阶段的能够接在 a[i] 前面的最大的状态值

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N = 3010;

int n;

int a[N], b[N];

int f[N][N];

int main()

{

    cin >> n;

    for (int i = 1; i <= n; ++ i)

        cin >> a[i];

    for (int i = 1; i <= n; ++ i)

        cin >> b[i];

    for (int i = 1; i <= n; ++ i)

    {

        int maxv = 1;

        for (int j = 1; j <= n; ++ j)

        {

            f[i][j] = f[i - 1][j];

            if (b[j] == a[i])

                f[i][j] = max(f[i][j], maxv);

            if (b[j] < a[i])

                maxv = max(maxv, f[i - 1][j] + 1);

        }

    }

    int res = 0;

    for (int i = 0; i <= n; ++ i)

        res = max(res, f[n][i]);

    cout << res << endl;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[最长上升子序列模型练习|最长上升子序列模型练习]] 🏠 [[00-刷题理模型]] ➡️ [[最长公共子序列|最长公共子序列]]