(LIS)最长上升子序列-二分优化

  • Post author:
  • Post category:其他


  • 最长上升子序列-二分优化


  • LIS定义:



一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的


。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8)

  • 实现思路:

动态规划:O(n^2)



设目前处于 i ,如果 a[i] > a[j] ,

如果 j+1~i-1 之间都是小于或者等于 a[j] 的数,那么此时 0~i 的最长上升序列等于 0~j 的最长上升序列 +1



如果 j+1~i-1 之间还有数大于a[j] ,那么取后者


得状态转移方程:


DP[i] = max( DP[i] , DP[j]+1 )


DP实现代码:

//DP
int LIS(int a[],int n)
{
    int DP[n];
    int Cnt=-1;
    memset(DP,0,sizeof(DP));
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
        {
            if(a[i]>a[j])      
            {
                DP[i]=max(DP[i],DP[j]+1);
                Cnt=max(DP[i],Cnt);   //记录最长
            }
        }
    return Cnt+1;   //因为初始化为0,所以结果+1

}

贪心+二分: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](

替换第一个大的原因是维护Array的递增性

),这样可以降低后面元素进入子序列的门槛



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

贪心二分实现代码:

//贪心+二分
int LIS(int a[])
{
    int Cnt=0;
    int Array[n+1];
    Array[0]=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]>Array[Cnt])
            Array[++Cnt]=a[i];
        else
        {
            int Index=lower_bound(Array,Array+Cnt+1,a[i])-Array;
            Array[Index]=a[i];
        }
    }
    return Cnt+1;   //实际长度需+1
}
  • 求最长下降子序列:



无需再写一个LDS—直接将要求的数组倒序,

倒序数组的最长上升子序列长度=原数组最长下降子序列长度



  • 最长不递减子序列—–扩展

定义:


在最长上升子序列的基础上,

允许

相同的若干元素

出现在子序列中

,在实际题目中也会出现,在实现上做点细节修改

原先实现细节变化:

DP:a[i] > a[j] —– a[i] >= a[j]     因为相同元素也会让序列变长

//最长不递减子序列
int LNDS(int a[],int n)
{
    int DP[n];
    int Cnt=-1;
    memset(DP,0,sizeof(DP));
    for(int i=0;i<n;i++)
        for(int j=0;j<i;j++)
        {
            if(a[i]>=a[j])      
            {
                DP[i]=max(DP[i],DP[j]+1);
                Cnt=max(DP[i],Cnt);   //记录最长
            }
        }
    return Cnt+1;   //因为初始化为0,所以结果+1

}

贪心+二分:a[i] > a[j] —– a[i] >= a[j]  ,改用 upper_bound



改用upper_bound的原因是

lower_bound 返回的是第一个大于等于 a[i]的地址

,在允许子序列有重复元素时


可能会造成相同元素覆盖


,使求得长度变短

//最长不递减子序列
int LDNS(int a[],int n)
{
    int Cnt=0;
    int Array[n+1];
    Array[0]=a[0];
    for(int i=1;i<n;i++)
    {
        if(a[i]>=Array[Cnt])
            Array[++Cnt]=a[i];
        else
        {
            int Index=upper_bound(Array,Array+Cnt+1,a[i])-Array;
            Array[Index]=a[i];
        }
    }
    return Cnt+1;
}



版权声明:本文为SZU_Crayon原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。