O(nlogn)LIS及LCS算法

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学长的倾情讲解

巴特西

O(nlogn)LIS及LCS算法

最新文章

热门文章