最长上升子序列详解（n方+nlogn）

先看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