给出1 2 ... N 的两个排列 ，求它们的最长公共子序列。
第一行是一个数 n。
接下来两行，每行为 n 个数，为自然数 1,2,n 的一个排列。
一个数，即最长公共子序列的长度。
5 3 2 1 4 5 1 2 3 4 5
3
题解
关于为什么可以转化成LIS问题，这里提供一个解释。
A:3 2 1 4 5
B:1 2 3 4 5
我们不妨给它们重新标个号：把3标成a,把2标成b，把1标成c……于是变成：
A: a b c d e
B: c b a d e
这样标号之后，LCS长度显然不会改变。但是出现了一个性质：
两个序列的子序列，一定是A的子序列。而A本身就是单调递增的。
因此这个子序列是单调递增的。
换句话说，只要这个子序列在B中单调递增，它就是A的子序列。
哪个最长呢？当然是B的LIS最长。
自此完成转化。
原文：https://www.cnblogs.com/donkey9/p/14842733.html