最长上升子序列问题LIS(dp)

灯珑LoGin

发布于 2022-10-31 13:55:49

3410

发布于 2022-10-31 13:55:49

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

题目：POJ3903

题意：有一个长为n的数列ai，需要求出这个序列的最长上升子序列的长度。上升子序列指的是对于任意i<j都满足ai<aj的子序列。

这题可以用dp来解

第一种dp方式

定义dp[i]为以 ai 结尾的lis的长度。那么，就有递推公式：

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

其中，j满足：j<i且aj< ai

那么，这样dp的时间复杂度为O(N2)

第二种dp方式

定义dp[i]为长度为i+1的lis中，末尾元素的最小值

上述定义是基于贪心的思想的，长度相同的lis，其末尾元素越小，那么可以接上新的元素成为长度+1的lis的可能性更大。因此，我们需要尽可能减小相同长度的lis的末尾元素值。

那么，基于这一假设，先把dp[i]初始化为INF，然后对其进行上述操作，即对于元素a[i]，将其更新至第一个末尾元素>=a[i]的lis的末尾，朴素算法的时间复杂度为 O(N2) .

显然，dp数组是单调增加的, 因此，可以使用二分搜索进行优化。这里我们使用algorithm内置的lower_bound函数。

AC代码：

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

#define MAXL 100005
#define INF (1 << 30)

int dp[MAXL];
int a[MAXL];

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

    int n;
    while (cin >> n)
    {

        fill(dp, dp + n, INF);

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

        for (int i = 0; i < n; ++i)
        {
            *lower_bound(dp, dp + n, a[i]) = a[i]; //dp中第一个大于等于a[i]的，接上a[i]
        }

        int ans = 0;

        ans = lower_bound(dp, dp + n, INF) - dp; //有dp[i+1]，则dp[i]不为inf，因此可以找第一个inf的位置，就可以确定最大的lis长度。
        cout << ans << endl;
    }
}

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年8月4日20，如有侵权请联系 cloudcommunity@tencent.com 删除

algorithm