最长上升子序列(LIS)的三种求法

57 阅读 0 评论 38 点赞

我是靠谱客的博主机灵发夹，最近开发中收集的这篇文章主要介绍最长上升子序列(LIS)的三种求法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

之前写LIS，只知道两种，一种最基础的n²，一种是n * log(n)的二分。

这两个应该人尽皆知。

但是如果权值如果不为1， n又非常大，则n²和二分都没法用了，

但是可以使用树状数组来维护（貌似也是人尽皆知），这种做法的思想跟第一种n²很像，大的值，可以由前面小

的值转移，这个时候使用树状数组维护，将原来的修改，求和改为最大值更新和获取即可。

具体含义即c[x]表示最大值≤x的最长子序列长度，当前添加的数字为x，则查询c[x - 1]即

最大值小于等于x-1的最长上升子序列，假设求得长度是y，则最大值大于等于x的最长上升子序列的长度都跟y + 1更新一次。

下面是三种LIS的求法

一

直接暴力求，从后往前扫(复杂度O(n²))

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define sz(a) ((int)(a).size())
typedef long long ll;
bool cmp(int a, int b) { return a > b; }
#define me(a, b) (memset(a, b, sizeof a))
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const int N = 2e5 + 10;
#define bo bool operator < (const node &oth)const

int a[N];
int b[N];
int main()
{
	int n;
	while (cin >> n)
	{
		memset(b, 0, sizeof b);
		int ans = 0;
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++)
		{
			b[i] = 1;
			for (int j = 1; j < i; j++)
			{
				if (a[i] > a[j])  // 若为非严格递增， 则改为>=
					b[i] = max(b[i], b[j] + 1);
			}
			ans = max(ans, b[i]);
		}
		cout << ans << endl;
	}
	return 0;
}

二

使用二分优化，每次选取最有潜力的上升子序列，复杂度(O(n * log(n)))

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define sz(a) ((int)(a).size())
typedef long long ll;
bool cmp(int a, int b) { return a > b; }
#define me(a, b) (memset(a, b, sizeof a))
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const int N = 2e5 + 10;
#define bo bool operator < (const node &oth)const

int a[N];
int d[N];
int main()
{
	int n;
	while (cin >> n)
	{
		memset(d, 0x3f, sizeof d);
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++)
		{
			int j = lower_bound(d + 1, d + n + 1, a[i]) - d; //若为非严格递增， 则改为upper_bound
			d[j] = a[i];
		}
		int len = lower_bound(d + 1, d + n + 1, 0x3f3f3f3f) - d - 1;
		cout << len << endl;
	}
	return 0;
}

三

使用树状数组维护前缀最大值，每次查询并更新前缀区间最大值。

#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define sz(a) ((int)(a).size())
typedef long long ll;
bool cmp(int a, int b) { return a > b; }
#define me(a, b) (memset(a, b, sizeof a))
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const int N = 2e5 + 10;
#define bo bool operator < (const node &oth)const

ll a[N];
ll c[N];
vector<ll>v;
inline ll lowbit(ll x)
{
	return x & -x;
}
void add(ll x, ll y, ll n)
{
	while (x <= n)
	{
		c[x] = max(c[x], y);
		x += lowbit(x);
	}
}
ll ask(ll x)
{
	ll res = 0;
	while (x)
	{
		res = max(res, c[x]);
		x -= lowbit(x);
	}
	return res;
}
int main(){
	ll n;
	while (cin >> n)
	{
		v.clear();
		me(c, 0);
		for (ll i = 1; i <= n; i++)
			cin >> a[i], v.push_back(a[i]);
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		ll ans = 0;
		for (ll i = 1; i <= n; i++)
		{
			ll x = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
			ll y = ask(x - 1);    // 若为非严格递增， 则改为查x
			ans = max(ans, y + 1);
			add(x, y + 1, n);
		}
		cout << ans << endl;
	}
	return 0;
}

掌握了第三种可以去做下这题。

https://ac.nowcoder.com/acm/contest/992/B

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef long long ll;
#define me(a, b) (memset(a, b, sizeof a))
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double PI = acos(-1);
const int N = 2e5 + 10;

ll a[N];
ll c[N];
vector<ll>v;
inline ll lowbit(ll x)
{
	return x & -x;
}
void add(ll x, ll y, ll n)
{
	while (x <= n)
	{
		c[x] = max(c[x], y);
		x += lowbit(x);
	}
}
ll ask(ll x)
{
	ll res = 0;
	while (x)
	{
		res = max(res, c[x]);
		x -= lowbit(x);
	}
	return res;
}
int main(){
	ll n;
	cin >> n;
	for (ll i = 1; i <= n; i++)
		cin >> a[i], v.push_back(a[i]);
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	ll ans = 0;
	ll num;
	for (ll i = 1; i <= n; i++)
	{
		cin >> num;
		ll x = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
		ll y = ask(x);
		ans = max(ans, num + y);
		add(x, num + y, n);
	}
	cout << ans << endl;
	return 0;
}