由于是经典模板了，话不多说，上代码。

#include<stdio.h>
#include<set>
#include<map>
struct LCS_ele_No_set
{
    int No[MAX_N];
    int Noc;
    void add(int a)
    {
        No[Noc++] = a;
    }
};
int n,Acount,Bcount;
int mem_DP[MAX_N][MAX_N];
int a[MAX_N], ClearedB[MAX_N], ClearedA[MAX_N];
int LIS[2*MAX_N],lis;
inline int max(int a, int b)
{
    return a > b ? a : b;
}
int findLIS(int a[], int n)//经典的最长上升子序列o(n*logN)算法
{
    int MaxLen = 0, _LIS[2*MAX_N];
    for (size_t i = 0; i < n; i++)
    {
        _LIS[i] = 10*MAX_N;
    }
    for (size_t i = 0; i < n; i++)
    {
        int left = 0, right = MaxLen + 1;
        while (left < right)
        {
            int mid = (left + right) / 2;
            if (_LIS[mid] >= LIS[i])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }
        _LIS[right] = LIS[i];
        MaxLen = max(MaxLen, right);
    }
    return n>0?MaxLen+1:0;
}
int main(void)
{
    while (scanf("%d", &n) != EOF)
    {
        std::set<int> ea;
        std::map<int, LCS_ele_No_set>  nb;
        for (size_t i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            ea.insert(a[i]);//记录ai的值，存进set方便比对
        }
        int Bcount=0;
        for (size_t i = 0; i < n; i++)
        {
            scanf("%d", &ClearedB[Bcount]);
            if (ea.count(ClearedB[Bcount])!=0)//a中没有的，不要
            {
                if (nb.count(ClearedB[Bcount])==0)//记录每个元素对应的序号
                {
                    LCS_ele_No_set temp;//nb中还没有的，创建
                    temp.Noc = 0;
                    temp.add(Bcount);
                    nb.insert(std::pair<int, LCS_ele_No_set>(ClearedB[Bcount], temp));
                }
                else
                {
                    std::map<int, LCS_ele_No_set>::iterator temp;//有的，追加序号
                    temp = nb.find(ClearedB[Bcount]);
                    temp->second.add(Bcount);
                }
                Bcount++;
            }
        }
        Acount = 0;
        for (size_t i = 0; i < n; i++)
        {
            if (nb.count(a[i])==1)//清理b中没有的元素
            {
                ClearedA[Acount++] = a[i];
            }
        }//-------------------------以上均为常规优化。
        //由于这一题是数字序列，会有不少只出现在一个数列的元素，清除它们
        lis = 0;
        for (size_t i = 0; i < Acount; i++)
        {
            LCS_ele_No_set tempNo;
            std::map<int, LCS_ele_No_set>::iterator iter;
            iter = nb.find(ClearedA[i]);//按照a的顺序枚举每一个既在a，又在b的元素
            tempNo = iter->second;//把他们在b中的序号
            for (int i = tempNo.Noc - 1; i >= 0; i--)//逆序输出
            {
                LIS[lis++] = tempNo.No[i];
            }
        }
        printf("%d\n", findLIS(LIS, lis));//LIS的长度既是所求LCS的长度
    }
    return 0;
}

那么，为什么这样的操作成立呢？

让我们看看这一个数列(假设 {P}_{i}{(A_j)} 是元素 A_j 在数列 B 中第 i 次出现时的序号：

\underbrace{{P}_{i}{(A_{1})}+{P}_{i-1}{(A_{1})}+\cdots+{P}_{2}{(A_{1})}+{P}_{1}{(A_{1})}}_{i}+\cdots+\underbrace{{P}_{k}{(A_j)}+{P}_{k-1}{(A_j)}+\cdots+{P}_{2}{(A_j)}+{P}_{1}{(A_j)}}_{k}

很明显，若 j 确定， {P}_{i}{(A_j)} 就是一个关于 i 的增函数，逆序后，同一个 A_i 所对应的数字中只能有一个中选。
对于中选的任何一个数字，都必然对应一个 B_i 且由于选取的是严格递增子序列，任何数字最多被选择一次。
由此，建立了严格上升子序列与公共子序列的唯一对应关系，LIS即为LCS，LIS又有 n\cdot log(n) 的算法，由此可以快速解决LCS问题。