动态规划之最长递增子序列

灯珑LoGin

发布于 2022-10-31 05:26:18

46400

代码可运行

文章被收录于专栏：龙进的专栏龙进的专栏

运行总次数：0

代码可运行

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

给定序列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;
}