线性DP

状态数组
$f[i][j]$：$a_1$~$a_i$,$b_1$~$b_j$以$b_j$结尾的最长公共上升子序列

转换方程

for(i:1~n){
        for(j:1~n){

            if(a[i]!=b[j])
                f[i][j]=f[i-1][j];

            if(a[i]==b[j])
                for(k:1~j)
                    if(b[k]<b[j])
                        f[i][j]=max(f[i][j],f[i-1][k]+1)
        }
    }

时间复杂度接近$o(n^3)$，题目中数据范围为$1≤N≤3000$，即接近$9×10^9$，会超时，所以进行优化。
在第三重循环中是要找一个值$b_k$小于$b_j$的$f[k][i-1]$的最大值，而这个值很明显之前有计算过，所以开一个变量存储这个值，在$a_i>b_j$的时候对这个最大值进行更新，那么当$j$循环到$b_j==a_i$的时候，$maxv$中存储的就是符合要求的的值。

    for(i:1~n){
        int maxv=1; //暂存最大值

        for(j:1~n){
            if(a[i]!=b[j])
                f[i][j]=f[i-1][j];
            if(a[i]==b[j])
                f[i][j]=max(maxv,f[i][j]);
            if(a[i]>b[j])
                maxv=max(maxv,f[i-1][j]+1);
        }
    }

C++ 代码

#include<iostream>

using namespace std;

const int N=3010;
int f[N][N],a[N],b[N];
int main(){
    int n;
    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++){

            if(a[i]!=b[j])
                f[i][j]=f[i-1][j];
            if(a[i]==b[j])
                f[i][j]=max(maxv,f[i][j]);
            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]);
    }
    cout<<res;

    return 0;
}