求一个数列的最长上升序列

　　动态规划法：O(n^2)

　　　　　　　

 1 //DP
 2 int LIS(int a[], int n)
 3 {
 4     int DP[n];
 5     int Cnt=-1;
 6     memset(DP, 0, sizeof(DP));
 7     for(int i=0; i<n; i++ )
 8     {
 9         for(int j=0; j<i; j++ )
10         {
11             if( a[i]>a[j] )
12             {
13                 DP[i] = max(DP[i], DP[j]+1);
14                 Cnt = max(DP[i], Cnt);//记录最长序列所含元素的个数
15             }
16         }
17     }
18     return Cnt+1;//因为初始化为0,所以返回结果+1
19 }

 

 

 

 

贪心+二分法：O(nlogn)　

分析：要让一个序列具有最长上升子序列，其实就是保证子序列中的每个元素尽可能小,降低门槛，让后面的元素尽可能多进入该子序列

实现：定义一个最长子序列数组Array，以及当前长度Len，从头到尾维护数组a

a. a[i]>Array[i]　（当前元素大于子序列结尾元素），则a[i]进入子序列：Array[++len] = a[i]

b. a[i]<=Array[i]，这时对Array进行维护，把Array中比a[i]大的第一个元素替换成a[i]（这样可以降低后面元素进入子序列的门槛。

c.　为了降低算法复杂度,因为Array是升序序列，所以用lower_bound查找Array中第一个大于等于a[i]的元素

 

 1 //贪心＋二分
 2 int LIS(int a[])
 3 {
 4     int Cnt=0;
 5     int Array[n+1];
 6     Array[0] = a[0];
 7     for(int i=1; i<n; i++ )
 8     {
 9         if( a[i]>Array[Cnt] )
10             Array[++Cnt]=a[i];
11             else
12             {
13                 int Index=lower_bound(Array, Array+Cnt+1, a[i])-Array;
14                 Array[Index]=a[i];
15             }
16     }
17     return Cnt+1;
18 }

 

 

求最长下降子序列：

　　　　不需要再写LDS---直接将要求的数组倒序，倒序数组的最长上升子序列长度＝原数组最长下降子序列长度。