最长递增子序列的问题就是:

给定序列A=a0,a1,a2,…,an,

如果它的子序列b1,b2,…,bn满足b1<b2<b3<…<bn

则称这个子序列是一个递增子序列。A的所有子序列中,最长的那个就是最长递增子序列(LIS)

这是一个经典的动态规划问题,我们可以用两种方法来解决。

第一种是比较笨的纯dp算法。时间复杂度为O(N2).

假设原序列存储于A[n+1]中,注意,序列从A[1]开始存储

方法是使用两个数组:

L[n+1]用于存储A[1]到A[i]中,部分元素构成的,且包含了A[i]的LIS的长度
P[n+1]存储上述LIS的倒数第二个元素在A中的下标

那么我们只需要执行以下步骤:

  • 不断寻找以当前位为结尾的子列的LIS
    • 寻找在这之前的LIS(满足最大元素小于当前元素)
    • 把当前元素加到上述LIS后端,更新L[i]、P[i]

光看文字有点绕,就看看代码吧:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define MAXN 100005

// a:存储输入的数据的数组
// l:以位i结尾且包含位i的LIS
// p:以位i结尾且包含位i的LIS的倒数第二位的坐标

ll a[MAXN] = {0}, l[MAXN] = {0}, p[MAXN] = {0};
int n;


bool cmp(const ll &a,const ll &b)
{
    return a>b;
}

ll dp()
{
    p[0] = -1;

    //当前正在找以第i位为结尾的LIS
    for (int i = 1; i <= n; ++i)
    {
        int k = 0;

        //找到之前的满足条件的LIS
        for (int j = 0; j < i; ++j)
        {
            if (a[i] > a[j] && l[j] > l[k])
                k = j;
        }

        p[i] = k;
        l[i] = l[k] + 1;
    }

    sort(l+1,l+n+1,cmp);

    return l[1];
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    
    cout<<dp()<<endl;
}

上面的算法已经能求解LIS问题了,只是它的时间复杂度高达O(N2),我们可以使用二分搜索来优化它。

使用二分搜索求解LIS的长度

主要思路:

用A[n]来存储原序列,第一个元素保存在A[0]

用L[i]来存储一个递增序列,每一位表示长度为i+1的递增子列的末尾最小值。不断考虑原数列的每一位,若其小于LIS的最大元素,则将其加到LIS末尾 ,否则,将LIS中第一个大于等于它的元素替换成它。(也就是相应长度的递增子列的末尾元素最小值)这样子保证了L数组是严格递增的。

我们希望借此能更新掉原来最长的子列的最大元素,这样才能为递增子列的延长提供便利。这也是本算法的核心。

这个算法就更绕了,其实就是在维护一个一维数组,使其每一位存储着长度为i的递增序列的最大元素。

这里要介绍C++中的两个函数

下界函数:lower_bound(first , last , v)
找到并返回 非降序列 [first,last) 中第一个大于等于v的元素的地址

上界函数:lower_bound(first , last , v)
找到并返回 非降序列 [first,last) 中第一个大于v的元素的地址

代码实现比较简单:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define MAXN 100005

int n;
int a[MAXN] = {0};
int L[MAXN] = {0};
int length = 0;

ll dp()
{
    length = 1;
    L[0] = a[0];

    /*
    *   主要思路:
    *       用L[i]来存储一个递增序列,每一位表示长度为i+1的递增子列的末尾最小值
    * 
    *       不断考虑原数列的每一位,若其小于LIS的最大元素,则将其加到LIS末尾
    *       否则将LIS中第一个大于等于它的元素替换成它。(也就是相应长度的递增子列的末尾元素最小值)
    *           我们希望借此能更新掉原来最长的子列的最大元素,这样才能为递增子列的延长提供便利。
    * 
    */

    for (int i = 1; i < n; ++i)
    {
        if (L[length - 1] < a[i])
            L[length++] = a[i];
        else
            *lower_bound(L, L + length, a[i]) = a[i];
    }

    return length;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    cout << dp() << endl;
}

总结一下,求LIS由两种方法,第一种O(N2)的做法速度慢,但是在求出LIS长度的同时,可以顺带找到LIS的完整序列。而第二种方法可以在O(nlogn)的时间复杂度内求出LIS的长度,但是不能找到LIS的完整序列。

转载请注明来源:https://www.longjin666.top/?p=875

欢迎关注我的公众号“灯珑”,让我们一起了解更多的事物~

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注