是个模板，
不是非常大的一个知识点，
最长上升公共子序列，
直接说最快做法N^2吧，
就是外循环i枚举第一个数组里遍历到的下标，
内循环j枚举第二个数组里遍历到的下标，
f[i][j]存a遍历到i,b遍历到j时的最长上升公共子序列长度，
如果a[i]!=b[j],f[i][j]=f[i-1][j]，显然因为i对答案没有贡献，所以加不加他都一样，
如果a[i]==b[j],f[i][j]=max(f[i-1][k])+1,k<j,就是从前面找一个最大的转移，这就比较显然了，
每次进行一遍内循环就计一次内循环里之前遇到的b[j]值小于a[i]值的最大f[i-1][j]，
如果遇到a[i]==b[j]就把f[i][j]更为记录的那个值+1，
正确性有保证因为前面记录的是合法的f值，也就是每一位都相互对应，而且算进答案的b[k]只有比a[i]小的，自然与b[k]相等且对应的a[l]比a[i]小，b[k]也比等于a[i]的b[j]小，如此得到的答案依然合法。

1
2
3
4
5
6
7
8
for(int i=1;i<=n;i++){
    ll tmp=0;
    for(int j=1;j<=m;j++){
        f[i][j]=f[i-1][j];
        if(b[j]<a[i])tmp=max(tmp,f[i-1][j]);
        if(a[i]==b[j])f[i][j]=tmp+1;
    }
}

很简短，
这就没了

顺带一提，
最长上升子序列有个lower_bound做法，
但我更喜欢值域线段树在线维护区间最大值，
线段树上存的是以下标为结尾的最长长度，
求答案就query前缀就好了，
然后再把当前的答案再插回去，
没准魔改一下树状数组可以去除大常数的问题。

最长公共子序列好像只有N^2?