基準(zhǔn)時(shí)間限制：1 秒 空間限制：131072 KB 分值: 0難度：基礎(chǔ)題
給出長(zhǎng)度為N的數(shù)組，找出這個(gè)數(shù)組的最長(zhǎng)遞增子序列。(遞增子序列是指，子序列的元素是遞增的）
例如：5 1 6 8 2 4 5 10，最長(zhǎng)遞增子序列是1 2 4 5 10。
Input
第1行：1個(gè)數(shù)N，N為序列的長(zhǎng)度(2?<=?N?<=?50000)
第2?-?N?+?1行：每行1個(gè)數(shù)，對(duì)應(yīng)序列的元素(-10^9?<=?S[i]?<=?10^9)
Output
輸出最長(zhǎng)遞增子序列的長(zhǎng)度。
Input示例
8
5
1
6
8
2
4
5
10
Output示例
5
問(wèn)題鏈接：1134 最長(zhǎng)遞增子序列
問(wèn)題分析：典型的計(jì)算最長(zhǎng)遞增子序列的問(wèn)題。
程序說(shuō)明：如果采用時(shí)間復(fù)雜度為O(n*n)的程序，是會(huì)出現(xiàn)TLE的。需要使用時(shí)間復(fù)雜度為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;
}
