ビルの飾りつけ (Building)
면접 대비시간 제한1초메모리 제한1024 MB
건물 높이가 순서대로 주어질 때, 가장 긴 순증가 부분수열의 길이를 구한다.
문제
国際情報オリンピックが日本で開かれることとなり，世界の選手達を歓迎するため，空港か ら宿泊施設までの道沿いにある高層ビルを飾りつけることにした．ある著名なデザイナーにデ ザインを依頼したところ，飾りつけに利用するビルは，空港から宿泊施設に向けて高くなって いく必要があると言った．つまり，飾りつけに利用するビルの高さを，空港に近いものから順 に h1, h2, h3, · · · とおくと，h1 < h2 < h3 < · · · となっていなければならない．
できるだけ飾りつけを華やかにするため，飾りつけに利用するビルの数をできるだけ多くし たい．入力として全てのビルの高さが与えられたとき，利用することのできるビルの数の最大 値を計算するプログラムを作れ．
입력
入力の 1 行目には，1 つの整数 n (1 ≤ n ≤ 1000) が書かれてい る．これは，空港から宿泊施設までの道のりにあるビルの数が n であることを表す．
次の n 行には，それぞれのビルの高さが書かれてる．i + 1 行目 (1 ≤ i ≤ n) には 1 つの整数 ai(1 ≤ ai ≤ 10000) が書かれている．これは，空港から i 個目のビルの高さが ai であることを 表す．
출력
出力は，標準出力に行うこと．飾りつけに利用することのできるビルの数の最大値 を表す整数を出力せよ．
힌트
ビルの総数が 9 であり、高さが空港に近いものから順に 3, 7, 5, 9, 8, 10, 10, 11, 9 である場合 を示したのが下図である。色をつけて示したビルを選ぶことにより、飾り付けに利用するビル の数を最大にすることができる。このときの最大値は 5 である。
