算法
(DP,线性DP,前缀和) $O(n^2)$
这道题目是AcWing 895. 最长上升子序列和AcWing 897. 最长公共子序列的结合版，在状态表示和状态计算上都是融合了这两道题目的方法。
状态表示：
f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合；f[i][j]的值等于该集合的子序列中长度的最大值；
状态计算（对应集合划分）：
首先依据公共子序列中是否包含a[i]，将f[i][j]所代表的集合划分成两个不重不漏的子集：
- 不包含
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；
- 子序列只包含
如果直接按上述思路实现，需要三重循环：
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])
{
int maxv = 1;
for (int k = 1; k < j; k ++ )
if (a[i] > b[k])
maxv = max(maxv, f[i - 1][k] + 1);
f[i][j] = max(f[i][j], maxv);
}
}
}
然后我们发现每次循环求得的maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。
因此可以直接将maxv提到第一层循环外面，减少重复计算，此时只剩下两重循环。
最终答案枚举子序列结尾取最大值即可。
时间复杂度
代码中一共两重循环，因此时间复杂度是 $O(n^2)$。
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3010;
int n;
int a[N], b[N];
int f[N][N];
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
for (int i = 1; i <= n; i ++ ) scanf("%d", &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 (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);
}
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);
printf("%d\n", res);
return 0;
}
朴素代码维护前缀的最大值的时候满足了 $a_i == b_j$，为什么优化后的代码维护前缀的最大值的可以不用满足？
我的理解是：优化之后的版本循环里面的两个if语句只会执行一个，第一个版本是在满足a[i]==b[j]的情况下，maxv会更新为f[i - 1][k]（k是满足a[i]>b[k]的下标最大的）；而第二个版本当a[i]大于b[j]的情况下，第一个if语句的条件显然不满足，maxv也更新为f[i - 1][j]，这里的j就充当了k的角色。
好问题，我也不懂
这个要问问y总，@yxc
主要是不可能A[i]>B[l]&&A[i]==B[l]
这里只是进行了代码的等效变换，maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值，朴素代码在 ai==bj时，每次都去计算前缀最大值，根本没有必要。可以发现这个前缀最大值与j无关，可以直接提到循环外迭代更新，没有必要再开一个循环去迭代n次寻找这个最大值，此时maxv的维护就不需要ai==bj，去寻找了，因为已经“记住了”。
这里的
a[i] > b[j]是为了维护b[1~j - 1]的满足小于a[i]的max吧，是为了记录f[1~i - 1][1~j - 1]。可能因为在maxv的维护过程中，a[i]是不会变的量，每一层a[i]都有与之对应的maxv，从下一个j来看，这一层的b[j]是包括在k中的，所以参与维护maxv
这个最大值最终还是为 f [ i ][ j ] 服务的，而只有在 ai == bj 的时候才会把这个最大值喂给 f [ i ][ j ] ，效果是一样的
优化后本质上也是求前缀最大值吧
maxv 也是 0~j - 1 里的最大值
优化后的版本是说，仅当a[i]大于当前b[j]的时候才会去更新maxv，这样当遍历到i这一层后面的b[jj]时，若a[i] == b[jj]，则一定有b[jj]>b[j]。这样满足了原代码的含义，即maxv是满足a[i] > b[k]的f[i - 1][k] + 1的前缀最大值。
懂了!
如果把后面if判断放在a[i]==b[j]这个判断里面就不行了，也就是说a[i]!=b[j]的时候这些数字要按你说的更新，但是a[i]==b[j]时怎么更新呢
两道基本题要钱！！！！！！！！！
可以到题库找的到的
还是要钱啊
看视频肯定要呀
提高课的题，买了才能看呢
乐扣有对应的不要钱
这状态定义谁想得到
需要很强的思维能力啊
要求以b[j]为结尾就很灵性
确实，正常人不容易想到
好难呜呜
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1); 这一行
为什么最后取最大值 f[i - 1][j]还要加1，
因为a[i]=b[j],所以公共序列长度加一
条件不是a[i] > b[j] 吗
因为枚举的是上一个位置
y总，这里好像还可以优化成一维，也过了😂，这里f[i][j]和f[i - 1][j]是等价的，因为必须得满足前面的a[i] = b[j]的条件，只需要用到i - 1的状态
我也这样想的
初始版本里面,只有当a[i]==b[j]的时候，才能用a[i]替换b[j],为啥优化完没有对此进行判断呢？
因为只有当这个条件满足时，maxv才会更新
提供一个在y总优化基础上的一维版本(其实就是很简单的一个等价变形，滚动数组):
单纯只是对于代码的变形，理解好是如何变形的就懂了
大佬们，为啥
if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1);这行代码中，既然是满足上升子序列，为什么不用要求i > j呢？兄弟，想明白了吗？
我对这点也很不明白
想多了吧....
所以为啥可以不用考虑呢？之前上升子序列的第二层for循环不就是
for (int i = 1; j < i; j ++ )吗？（不过下面好像有人已经解答过了，之前没注意hh）下面好像之前已经有人解释过了，可以看看下面的评论（虽然可能还是需要自己再理解下hh）
嗯嗯，我现在差不多理解了
https://www.acwing.com/solution/content/125789/ 你看看这种说法呢
谢谢hxd
客气
因为只能接在前面比自己小的数字后面，到底哪个数字比自己小，不判断不知道噢~我们在第一层循环控制下，是a[i]不变的，其实就是找小于a[i]的遍历b[j]的val最大值。
for里i>j啊
因为O(n^3)的第三层循环枚举的j是第二层的子集
感谢 j 看作倒数第二项
有了这行以后应该说是以a[i]为结尾的最大值更对吧，因为a[i]为结尾值才能用b[j]与其比较判断是否是可选项
不是的，状态定义的是以
b[j]结尾，只是这里a[i]与b[j]相等而已。建议先理解暴力做法，然后优化做法单纯只是对暴力的等价变形，而与原问题中状态的定义无关，这样理解会更加清楚。懂了，谢谢
if(a[i]==b[j])f[i][j]=max(f[i][j],maxv+1);
这么写为啥是错误的啊
当maxv的最大值是1时，你在最后又加个1，那就变成2了。
为什么最后要遍历一下 而不是直接输出f[N][N] 它不是代表a的最后一个字符与b的最后一个字符的结果嘛 包含所有的f
f[i, j]表示的是在b[]中以b[j]结尾的公共子序列，但是最优解不一定以b[N]结尾，所以需要枚举所有可能的情况。明白了，谢谢老师！
rtdh
ai==bj
没想到我居然看懂了
妙哇
终于搞明白了
%%%%%
解释一下为什么i和i-1都能ac。优化版中有
f[i][j] = f[i - 1][j]，所以if (a[i] > b[j]) maxv = max(maxv, f[i - 1][j] + 1)里的f[i-1][j]也可以写成f[i][j]。同理朴素版中f[i - 1][k]也可以写成f[i][k], 有代码a[i] > b[k], 当k作为j被执行时, 不会执行a[i] == b[j]后面的代码。第一个朴素版，
for循环中k要从0开始，不然f[i][1]始终为0显然是不对的不需要 maxv初始为1的