求一个数列的最长非递增（递减）子序列

 

问题描述： 给出一个数列，找出其中最长的单调递减（或递增）子序列。比如数列 4，2，6，3，1，5  最长递增子数列为2,3,5  

            相似的问题：1求最大和的子序列

                              2最大公共子串

                              3最大公共子序列

            注意：串与序列的关系，，串是连续的，而序列则不可以。。。

 

解决办法 ：在网上得到两种解法

解法一：

 

首先将这个序列进行排序，然后再求出已排序的和未排序的这两个数列最长公共子序列

 

解法二：就是用动态规划法来解决问题：

            我们假设原数列定义为数组a[]，然后定义一个数组b[i],表示以a[i]结尾的最长公共子序列的长度,只要求出所有的b[i]数组也就可以确定最长的公共子序列，

            那么我们根据已经求出的b[0]--b[i-1]，来求b[i]呢，，也就如何求出以a[i]结尾的最大公共子序列的长度呢，

            此时在a[0]-a[i-1]范围内，已经求出多个长度的公共子序列，且最大长度的一个序列的长度为s，这个序列的最后一个元素为t，那么

            1.如果a[i]<t ,那么当前最大子序列的长度为s+1，而且这个序列的最后一个元素就是a[i],即b[i]=s+1

            2.如果a[i]=t，那么这个子序列的长度不变，仍为s，b[i]=s;

            3.如果a[i]>t,这时候就会比较的麻烦了，因为a[i]不可能成为长度为s的最长公共子序列的最后一项了，然后与一个长度为s-1的公共子序列的最后一项进行比较。。直至小于某一个长度为s1的子序列的最后一个元素t1，

 

               如果a[i]仍然大于t1，那么就继续向长度更小的子序列的最后一个元素进行比较，知道找到一个合适的子序列长度s2，那么此时b[i]=s2+1；如果a[i]比所有的以求子序列的最后一个元素都大话，那么最后就赋值b[i]=1;即以该元素为结尾的子序列长度为1.

              那么如何保存这些已经查找出来的子序列的最后一一个元素呢  ，我们定义一个数组c[],即c[i]就是代表长度为i的当前最长子序列的最后一个元素，我们最终的元素超找比较就是在c[]数组中进行的，b[i]最后可以用于最终的最长子序列的输出。

 

               按照上述的条件得到的c[i]肯定是单调递增或者递减的，如果采用二分查找的话那么时间复杂度为O(n*lgn)..

 

动态的转移公式为：

假设f(i)代表以a[i]结尾的最长单调自增子序列的长度：

        /    f(i-1)+1                                          , a[i]>a[i-1]

f(i)= ---  f(i-1)                                               ,a[i]==a[i-1]

        \   max(max({f(j)|a[i]<a[j],i>j}+1),1)  ,a[i]<a[i-1]

 

 

比如查找 4，2，6，3，1，5 的最长递减子数列过程如下：

最终的数组b[]={1,2,1,2,3,1}

数组c[]={-1,6,5,1,-1,-1,}

 

具体的算法如下：

void getArray(int *a,int length)
{
	int *b=new int[length]; //b[i]表示以a[i]结尾的最长递减子序列的长度
	int *c=new int[length];//数组c[i]表示长度为i的递减子序列的末尾值的最大值
	int s=1;//s表示目前为止最长单调序列的长度
	int k=1;
	for(int i=0;i<length;i++)//初始化b
	{
		b[i]=-1;
	}
    c[1]=a[0];
	for(int j=0;j<length;j++)
	{
               k=BinFind(c,s,a[j]);
	  if(k>s)
	  {
		  s++;
	  }
	  c[k]=a[j];
	  b[j]=k;
	}
    print(a,b,s,length);//根据数组b[]来打印最长子序列
}

 

 

void print(int *a,int *c,int s,int length)//从后向前查找，并打印出来
{
	int i=length;
    while(s>0)
	{
	   while(c[i]!=s&&s>0)
	   {
		  if(i<=0)
		  {
			  break;
		  }
	      i--;
	   }
	   printf("%d ",a[i]);
	   s=s-1;
	   i--;
	}
	
}

 

 

 

下面在来说下几个相关的问题：

1.最大子序列问题

   就是求出连续的子序列的和最大，数组中有正数也有负数。。。。这个问题在之前已经描述过了。。

   就是遍历数组，保证序列的前面部分的和为大于零

   最后比较每个序列的和的大小并选择之

2.最长公共子串（LCS）

 

   这个问题主要是找出两个序列之中相同的最长的连续子串比如：abcad  abaad  最长公共子串包括ad与ab

 

  如何解决这个问题呢：

  在网上见到一个比较新颖的解决方案：用矩阵的形式，如下：

 以一个二维数组来表示对应位置相同的位1，不同的为零

  　   b　　a　　b

c　　0　　0　　0

a　　0　　1 　　0

b　　1 　　0　　1

a　　0　　1 　　0

 

可以看见相同的子序列在一条斜线上都为1.所以最长公共子序列为ab，ba

在这种二位数组中寻找这种相同的元素也是比较困难的，，所以就修改到如下方式：

　　  b　　a　　b

c　　 0　　0　　0

a　　0　　1 　　0

b　　1 　　0　　2

a　　0　　2 　　0

 

把斜线上的1加到加到最后一个元素位置上，但是考虑到算法的效率，这样会浪费很多无谓的空间，所以我们使用一维数组来描述二维数组：

 

定义两个一位数组，我们按行进行初始化，其中一个数组保存上一行的数据，另外一个数组保存当前行的数据，当前行的数据就是通过上一行来进行计算，最后找出最大的值

 

 

 

2.最长公共子串（LCS）

最常用的就是动态规划法：

 

 

           /      0                               if i<0 or j<0
c[i,j]=---          c[i-1,j-1]+1                    if i,j>=0 and xi=xj
           \      max(c[i,j-1],c[i-1,j]           if i,j>=0 and xi≠xj

 

 

使用s[i][j]数列来保存c[i][j]使用上述哪种方式得到的，，，最后找出s[i][j]中所有位1为i,j（即是由i-1，j-1得到的c[i][j]）