【题目描述】
给定N个数，求这N个数的最长上升子序列的长度。
也就是说，对于给定的序列，保持序列的原有输出不变，从中挑选出一个子集，使其可以满足从小到大的顺序，比如说下面的 2 3 就是符号要求的上升序列，但是 3 5 不行，因为顺序发生了交换。
【样例输入】
7
2 5 3 4 1 7 6【样例输出】
4 // 即 2 3 4 7 或者 2 3 4 6一共有两种方法，采用的都是动态规划的思想。
第一种方法说的是，用 dp[i] 来表示一个状态，表示前 i 个元素的最长上升序列的长度，对于第 i + 1 个元素，其实就是跟前 i 个元素去比较，如果第 i + 1 个元素比前面某个元素大，比如这个元素是 j ，那么 dp[i+1] 更新为 dp[j] + 1 。相当于原来的 j 形成的序列后又接入了第 i 个元素，即状态转移方程（这个状态转移方程不全，还必须满足元素的大小关系）
那么这种算法的时间复杂度（因为是双重循环）就是 $O(n^2)$ ，代码如下
# include <bits/stdc++.h>
using namespace std;
int dp[1005];
int n;
int a[1005];
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
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;
}这种算法其实是可以优化的，因为在原理的状态转移方程中
实现 max 的算法采用的是内层循环，但是如果采用二分查找来实现找到最大的值的方法，那么就会获得 $O(n\log n)$ 的复杂度，为了实现二分查找，可以采用贪心策略：所以每遇到一个比栈顶元素大的数，就放进栈里，遇到比栈顶元素小的就二分查找前边的元素，找到一个“最应该被换掉的元素”，用新数去更新前边的元素。这个元素可能不是最优解的一部分，但是它可以使得后面还未加入的、比较小的数更有可能进入这个队列。通俗地来说，作为门槛，他本来要大于当前序列的最后一个数才能加进去；就是如果我太大了，我就乖乖呆在末尾；如果前面有一个数比我大，也就是我比你好，既然我在你后面也就是我们两者只能选其一，那我只好把你替换掉了。虽然我这临时临头换的不一定最合适，但是对于后面还有很多的人等着排进来的情况下，我给他们创造了更多机会，使得这个序列的最后一个数有可能变小，让更多的人进来。
具体代码如下：
# include <bits/stdc++.h>
using namespace std;
int stk[1005];
int top;
int n;
int a[1005];
int main()
{
cin >> n;
for(int i = 0; i < n; i++)
{
cin >> a[i].l >> a[i].w;
}
stk[top++] = a[0];
for(int i = 1; i < n; i++)
{
if(stk[top - 1] < a[i])
{
stk[top++] = a[i];
}
else
{
*(lower_bound(stk, stk + top, a[i])) = a[i];
}
}
cout << top;
return 0;
}此外，根据dilworth定理，不下降子序列最小个数等于最大上升子序列的长度。