LCS -> LIS
算法思路
第一个序列A中所有元素均不重复.
设第二个序列B中元素在A中对应位置为k(不存在则为-1),k构成数组B'.
考虑A与B的公共子序列CS和B'的上升子序列IS:
任意CS:
公共子序列对应B中元素{b1,b2,...,bk}在A中位置{b'1,b'2,...,b'k}单调递增. CS->IS.
任意IS:
不考虑-1的情况,任意一个单调递增序列{b'1,b'2,...,b'k}对应位置B中元素{b1,b2,...,bk}在
A中是单调上升的,所以{b1,b2,...,bk}是一个CS. IS->CS.
CS与IS一一对应,所以求LCS可以转换为LIS求解.
时间复杂度
O(nlogn)
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int n;
int a[N], b[N], id[N], q[N];//id[i]:a[i]的位置 q[]:维护一个贪心的上升序列
int main()
{
memset(id,-1,sizeof id);
scanf("%d",&n);
for( int i = 0; i < n; i++ ) scanf("%d",&a[i]), id[a[i]] = i;
for( int i = 0; i < n; i++ ) scanf("%d",&b[i]);
int tt = 0;
//q[0]作为最小值的哨兵 实际上不加也可以 因为mid上取整
//第一次l=r=0 dp[1] = k 之后mid最小值为1 不会用到0
for( int i = 0; i < n; i++ )
{
int k = id[b[i]];
if( k == -1 ) continue;
int l = 0, r = tt;
while( l < r )
{//找到<k的最大值(如果用>=k的最小 q[]中可能不存在)
int mid = l + r + 1 >> 1;
if( q[mid] < k ) l = mid;
else r = mid - 1;
}
q[l+1] = k;
tt = max( tt, l+1 );
}
printf("%d\n",tt);
return 0;
}