一，题目

       求一个数组的最长递减子序列

               比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2}

      

       求一个数组的最长递增子序列

               比如{1，-1，2，-3，4，-5，6，-7}的最长递减子序列为{1，2，4，3，6}

             

二，递增序列长度求解方法

       解法一：

                     时间复杂度为 o（n^2）

                     遍历数组序列，每遍历一个数组元素，则求序列到当前位置 最长的递增序列数，用temp[i]存储。

                     注意，当前的最长递增子序列受已经遍历的最长递增子序列影响，从序列头 再遍历到当前位置的前一个位置，挨个比较 a[j]与a[i](当前元素)大小，遇到小于a[i]且判断需要更新

ｔｅｍｐ［］数组。

　　　　　由于这里仅仅是求，最长递增序列的长度，所以仅仅用ｔｅｍｐ［］存储长度大小。

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  源码：

 

#include 
    
     using namespace std;int LIS(int array[],int n){	int temp[n];//存放当前遍历位置最长序列 	for(int i=0;i
     
      array[j]  && temp[j]+1 > temp[i] )			{				temp[i] = temp[j] + 1;			}					}	}		int max=temp[0];	for(int k=0;k
     
    

       解法二：时间复杂度任然为　Ｏ（ｎ＾２）

　　　　　　为了减少比较次数

　　　　　　采用空间换时间的策略。新增一个数组ＭａｘＶ［］，ｍａｘ［ｉ］表示所有长度为ｉ的递增子序列中最大值之间的最小值

　　　　　　ｎＭａｘｌａｘ记录当前最长子序列

　　　　　　每次遍历一个元素时候，从最长子序列开始遍历，一直到１　比较当前元素值ａｒｒ［ｉ］　跟ＭａｘＶ［ｊ］的值，从而更新ｔｅｍｐ［］最长子序列和ｎＭａｘＬａｘ和ＭａｘＶ［］的值

　　源码：

#include 
    
     using namespace std;int LIS(int array[],int n){	int temp[n];//存放当前遍历位置最长序列 	int  MaxV[n]; //最长子序列中最大值之间的最小值	MaxV[1]=array[0];//初始序列长度为1的子序列 中最大值的最小值    MaxV[0]=-9999;//边界值	 	 for(int i=0;i
     
      =0;--j) //找出前面最长的序列 		{			if(array[i]>MaxV[j])//当前值大于长度为j的子序列中最大值之间的最小值 			{				temp[i] = j + 1;				break; 			}					}				if(temp[i]>nMaxLis)//在最长子序列时停止 （这时只有一个最长的） 		{			cout<<"nMaxLIs"<
      
       <
      
     
    

　　解法三：

　　　　　　将内循环查询部分换成二分搜索，则时间复杂度降低为　Ｏ（ｎｌｏｇＮ）

                   

 

三，递减序列　最长子序列求解方法

        用index数组，从大到小排序。然后依次遍历元素，查找元素在index数组中的位置pos ，根据位置来判断当前最长的子序列。

 

#include
    
     #include
     
      #include
      
       using namespace std ;int BiSearch(int *A,int nTarget,int nLen);void FindLongestSequence(int *A,int nLen){	int *index=new int[nLen];//存放子序列 	int *LDS=new int[nLen];		index[0]=A[0];	LDS[0]=1;	int indexLen=1; //最长递增子序列 长度 		for (int i=1;i
       
        =indexLen)//插入的当前位置大于最长序列 			indexLen++;	}		int ResultLen=indexLen;	for (int i=nLen;i>=0;i--)//记录最长递减子序列 	{		if(LDS[i]==ResultLen)		{				index[ResultLen-1]=A[i];			ResultLen--;		}			}	for (int i=0;i
        
         0);	int start=0;	int end=nLen-1;	while (start<=end)	{		int mid=(start+end)/2;		if(nTarget>A[mid])			end=mid-1;		else if(nTarget