欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

最长上升子序列详解(n方+nlogn)

程序员文章站 2022-06-24 18:46:43
先说n方的算法。定义一个二维数组dp[maxn].dp[i]代表结尾下标为i时最长最长上升子序列的长度。若要确定dp[i]的值,只需要遍历dp[1] to dp[i - 1]即可,时间复杂度n方。状态转移方程:dp[i] = max(dp[i], dp[j] + 1) //a[i] > a[j]代码:#include #include #include #include

先看n方的算法。
定义一个二维数组dp[maxn].dp[i]代表结尾下标为i时最长最长上升子序列的长度。
若要确定dp[i]的值,只需要遍历dp[1] to dp[i - 1]即可,时间复杂度n方。
状态转移方程:

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

代码:

#include <iostream>
#include <algorithm>
#include <set>
#include <stack>
#include <cstring>
using namespace std;

const int maxn = 1e5 + 10;
int a[maxn];
int dp[maxn]; 

int main() {
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	int ans = 0;
	for(int i = 1; i <= n; i++) {
		dp[i] = 1;
		for(int j = 1; j < i; j++) {
			if(a[i] >= a[j] && dp[j] + 1 > dp[i])
				dp[i] = dp[j] + 1, ans = max(ans, dp[i]); 
		}
	}
	cout << ans;
	return 0;
}

接下来看nlogn的算法:
定义一个栈,st[maxn]。st[i]代表最长上升子序列长度为i时最小的最后一位为多少。在遍历原序列的过程中,若a[i] > st[len],则把a[i]入栈,否则用二分找出栈中大于a[i]的第一个数,并替换为a[i].最后,len即为最长上升子序列的长度。

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn = 1e5 + 10;
int a[maxn];
int st[maxn];
int n;

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++)	cin >> a[i];
	int len = 1;
	st[len] = a[1];
	for(int i = 2; i <= n; i++) {
		if(a[i] > st[len])	st[++len] = a[i];
		else {
			int id = lower_bound(st + 1, st + 1 + len, a[i]) - st;
			st[id] = a[i];
		}
	}
	cout << len; 
	return 0;
}

本文地址:https://blog.csdn.net/ln2037/article/details/110245874

相关标签: dp