基准时间限制：1 秒 空间限制：131072 KB 分值: 0难度：基础题
给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）
例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。
Input
第1行：1个数N，N为序列的长度(2 <= N <= 50000)
第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)
Output
输出最长递增子序列的长度。
Input示例
8
5
1
6
8
2
4
5
10
Output示例
5
问题链接：1134 最长递增子序列
问题分析：典型的计算最长递增子序列的问题。
程序说明：如果采用时间复杂度为O(n*n)的程序，是会出现TLE的。需要使用时间复杂度为O(nlogn)的程序。
AC的C++程序如下：
[cpp]view plaincopy
#include
usingnamespacestd;
constintN = 50000;
intstack[N+1], ps;
intmain()
{
intn, val;
while(cin >> n) {
ps = 0;
for(inti=1; i<=n; i++) {
cin >> val;
intleft=1, right=ps, mid;
while(left <= right) {
mid = (left + right) / 2;
if(val > stack[mid])
left = mid + 1;
else
right = mid - 1;
}
stack[left] = val;
ps = max(ps, left);
}
cout << ps << endl;
}
return0;
}
