最长递增子序列【LIS】

基准时间限制：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;

}