2.1 法一：$O(N^2)$

令 $dp[i]=$ 以 $a_i$ 结尾的上升子序列的最大长度。
以 $a_i$ 结尾的上升子序列有两种可能：

• 1、仅有 $a_i$ 一个元素
• 2、在满足 $j<i$ 且 $a_j<a_i$ 的以 $a_j$ 结尾的上升子序列结尾，加上 $a_i$

所以，递归方程为：

$$dp[i]=max(1,dp[j]+1),j<iand{a}_j<a_i$$

最终结果是 $dp[i]$ 的最大值。

---

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 5e3 + 3;
int A[MAX], n, dp[MAX];

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	n = quickin();
	for (int i = 0; i < n; i++)
		A[i] = quickin();
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		dp[i] = 1;
		for (int j = 0; j < i; j++)
		{
			if (A[j] < A[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		ans = max(ans, dp[i]);
	}
	cout << ans << endl;
	
	return 0;
}

---

2.2 法二：$O(NlogN)$

令 $dp[i]=$ 长度为 $i+1$ 的上升子序列的末尾元素的最小值。（因为对于相同长度的上升子序列，结尾元素越小，就越有优势）
对于每个 $dp[i]$，遍历 $a_j$，若 $i==0$ 或 $a_j>dp[i-1]$，不断更新 $dp[i]=min(dp[i],a_j)$。最终，使 $dp[i]<INF$ 的最大的 $i+1$ 就是所求。如果按这个思路，仍然是 $O(N^2)$。

因为 $dp[i]$ 是升序，所以我们可以选择用二分搜索来优化。遍历 $a_j$，在 $dp[i]$ 中查找首个不小于（lower_bound） $a_j$ 的 $dp[i]$ ，并赋值 $a_j$。最终，使 $dp[i]<INF$ 的最大的 $i+1$ 就是所求。

---

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int quickin(void)
{
	int ret = 0;
	bool flag = false;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if (ch == '-')    flag = true;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9' && ch != EOF)
	{
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	if (flag)    ret = -ret;
	return ret;
}

const int MAX = 5e3 + 3;
const int INF = 1e8;
int A[MAX], n, dp[MAX];

int main()
{
	#ifdef LOCAL
	freopen("test.in", "r", stdin);
	#endif
	
	n = quickin();
	for (int i = 0; i < n; i++)
		A[i] = quickin();
	
	fill(dp, dp + n, INF);
	for (int i = 0; i < n; i++)
	{
		*lower_bound(dp, dp + n, A[i]) = A[i];
	}
	cout << lower_bound(dp, dp + n, INF) - dp << endl;
	
	return 0;
}

---

完