morestep学长出题，考验我们，第二题裸题但是数据范围令人无奈，考试失利之后，刻意去学习了下优化的算法
一、O（nlogn）的LIS（最长上升子序列）
设当前已经求出的最长上升子序列长度为len。先判断A[t]与D[len]。若A [t] > D[len]，则将A[t]接在D[len]后将得到一个更长的上升子序列，len = len + 1， D[len] = A [t]；否则，在D[1]..D[len]中，找到最大的j，满足D[j] < A[t]。令k = j + 1，则有A [t] <= D[k]，将A[t]接在D[j]后将得到一个更长的上升子序列，更新D[k]
= A[t]。
不过这种方法要注意，D[]中并不是我们所求的最长上升子序列
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int search(int *a,int len,int n)
{
int right=len,left=0,mid=(left+right)/2;
while(left<=right)
{
if (n>a[mid]) left=mid+1;
else if (n<a[mid]) right=mid-1;
else return mid;
mid=(left+right)/2;
}
return left;
}//二分查找 int main()
{
int a[1000]={0},b[1000]={0};
int n,i,j,mid,len;//len用来储存每次循环结束后已经求出值的元素的最大下标
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%d",&a[i]);
b[1]=a[1];
b[0]=-1;
len=1;//从第一位开始，目前只有第一位，所以len=1
for (i=1;i<=n;i++)
{
j=search(b,len,a[i]);
b[j]=a[i];
if (j>len) len=j;//更新len，由二分查找可知 ，len其实只须＋1.....
}
printf("%d",len);
return 0;
}
二、O（nlogn）的LCS
其实就是把两个序列化成一个序列，然后做一遍上述O（nlogn）的LIS即可
转换方法如下：
有样例
7 8
1 7 5 4 8 3 9
1 4 3 5 6 2 8 9
数组a中 1 2 3 4 5 6 7
分别对应1 7 5 4 8 3 9 不妨在数组b中的相同的数用在数组a中的 下标来表示（没有出现的用0）
由上述描述则数组b原来为： 1 4 3 5 6 2 8 9
可以表示为： 1 4 6 3 0 0 5 7
然后对处理后的数组进行一遍LIS，LIS中的len即为所求
注意：这种O（nlogn）的LCS只适用于两两互不相同的两个序列之中，不然会退化（但可以维护二叉搜索树，然而我并不会/(ㄒoㄒ)/~~），但这种LIS是可重的
下面是代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[100000]={0},c[100000]={0},d[100000]={0}; int search(int *a,int len,int n)
{
int right=len,left=0,mid=(left+right)/2;
while(left<=right)
{
if (n>a[mid]) left=mid+1;
else if (n<a[mid]) right=mid-1;
else return mid;
mid=(left+right)/2;
}
return left;
}//二分查找 int main()
{
int n,m,i,j,mid,len;
scanf("%d%d",&n,&m);
for (i=1; i<=n; i++)
{
scanf("%d",&a[i]);
c[a[i]]=i;
}
for (i=1; i<=m; i++)
{
scanf("%d",&a[i]);
a[i]=c[a[i]];
}
d[1]=a[1];
d[0]=-1;
len=1;
for (i=1;i<=m;i++)
{
j=search(d,len,a[i]);
d[j]=a[i];
if (j>len) len=j;
}
printf("%d",len);
return 0;
}
此处感谢morestep学长的倾情讲解