最长上升子序列

题目链接：https://www.acwing.com/problem/content/898/

题目描述

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入描述

第一行包含整数 N。
第二行包含 N 个整数，表示完整序列。

输出描述

输出一个整数，表示最大长度。
1≤N≤100000
−1e9≤数列中的数≤1e9

示例

输入

7
3 1 2 1 8 5 6

输出

4

分析

约定

记第i个数字为a[i]

状态表示

f(j)表示以第j个数字为结尾的子序列的最大长度

状态划分与计算

显然，f(j)所对应的最长子序列的最后一个元素为a[j]。
那第二个元素是谁呢？这就是我们划分的关键。第二个元素可以是前j-1个数字中任意一个比a[j]小的数字，枚举所有情况并计算，取最大值就是答案！

状态转移方程

由上一步的分析，我们得到状态转移方程如下：
f(j)=max(f(i))+1    (1 <= i < j , a[i] < a[j])

优化

朴素解法中，求解每一个f(j)都要去遍历[1,j-1]，这就很不好。
思考一下，对于一个长度为3的子序列，其最后一个元素为10，另一个长度为3的子序列，其最后一个元素为8，那么在两子序列之后的元素再考虑能否出现长度为4的子序列时只需要比较其和8的大小，大于就可以变成长度为4的子序列。
因此，我们可以发现，对于同样长度的子序列，我们仅需要关注各序列末端元素的最小值即可。这就启发我们维护各长度子序列末端元素的最小值。
设定一个数组s，s[i]表示长度为i的子序列末端元素的最小值，变量len表示已知子序列的最大长度。易得该数组的元素单调递增。
从前到后遍历a，对于a[j]，找到第一个大于等于a[j]的s[i],若存在这样的s[i]，满足i<=len：

• a[j] < s[i]，令s[i]=a[j]
• a[j] >= s[i]，不处理

若不满足，则执行len++，另a[len]=a[j]。

朴素解法代码

---

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1001;

int n;
int a[N];
int f[N];

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

	for (int i = 1; i <= n; i++)
	{
		f[i] = 1;		//注意初始化
		for (int j = 1; j < i; j++)
		{
			if (a[i] > a[j])
				f[i] = max(f[i], f[j] + 1);
		}
	}
	int res = -1e9;
	for (int i = 1; i <= n; i++)
		res = max(res, f[i]);
	cout << res << endl;
	return 0;
}

优化解法代码

---

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

const int N = 100001;

int n;
int a[N];
int len;
int s[N];
int main()
{
	s[0] = -1e9 - 1;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		int l = 0, r = len;
		int p = lower_bound(&s[l], &s[r] + 1, a[i]) - (&s[l]);
		s[p] = a[i];
		if (p > len)
			len++;
	}
	cout << len << endl;
	return 0;
}