(LIS)最长上升序列(DP+二分优化)

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

  动态规划法: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---直接将要求的数组倒序,倒序数组的最长上升子序列长度=原数组最长下降子序列长度。

 

上一篇:Day 08 可变与不可变对象/列表与字典内置方法


下一篇:bind使用场景