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

- 日理万妓 2022-05-15 04:55 238阅读 0赞

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

--------------------

*  ## 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;
    }