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; }