PKU 3903 Stock Exchange

問題。

数列が与えられる。最長増加部分列の長さを求めよ。

方針

おなじみの最長増加部分列。
dp[i]に長さi+1の増加列の最後尾をもっておき、更新していく。
O(nlogn).

int n,a,dp[100001];

int main()
{
	while(~scanf("%d",&n)){
		rep(i,n)dp[i]=inf;
		rep(i,n){
			scanf("%d",&a);
			*lower_bound(dp,dp+n,a)=a;
		}
		printf("%d\n",lower_bound(dp,dp+n,inf)-dp);
	}
	return 0;
}