LCIS是最长公共上升子序列,具有公共子序列,以及上升子序列的性质。
定义$f_{i,j}$表示$A_i\sim A_i$与$B_1 \sim A_j$可以构成的以$B_j$为结尾的最长公共子序列的长度。
显然地,
当$A_i\ne B_j$时,$f_{i,j}=f_{i-1,j}$(因为强制以$B_j$结尾)
当$A_i=B_j$时,$f_{i,j}=\max\limits_{0\le k<j,B_k<B_j}\{ f_{i-1,k}\}+1=\max\limits_{0\le k<j,B_k<A_i}\{ f_{i-1,k}\}+1$
打成代码

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(a[i]==b[j])
            for(int k=1;k<j;k++)
                if(b[k]<a[i])f[i][j]=max(f[i][j],f[i-1][k]+1);
        else f[i][j]=f[i-1][j];
    }

仔细观察发现,j是线性增长的,k随着j增大而增大,新的状态可以进入决策状态,则可以改写成这个代码。

for(int i=1;i<=n;i++)
    {
        int val=0;
        if(b[0]<a[i])val=f[i-1][0];
        for(int j=1;j<=n;j++)
        {
            if(a[i]==b[j])f[i][j]=val+1;
            else f[i][j]=f[i-1][j];
            if(b[j]<a[i])val=max(val,f[i-1][j]);
        }
    }