時間制限:2000ミリ秒
メモリ制限:65536KB
問題
数列a が、a 1 < a 2 < . . . < a N を満たすとき、数列a を「順序付けられている」と呼ぶことにする。数列
(a 1 , a 2 , . . . , a N ) が与えられたとき、1 <= i 1 < i 2 < . . . < i K <= N を満たすなら、数列(a i 1 , a i 2 , . . . , a i k ) は
それの部分列である。例えば、数列(1, 7, 3, 5, 9, 4, 8) は、順序付けられた部分列を持つ。例えば、(1, 7), (3, 4, 8)
などである。最も長い「順序付けられた部分列」は長さが4で、(1, 3, 5, 8) である。
数列が与えられたとき、その数列の最も「長い順序付けられた部分列」の長さを求めるプログラムを作成せよ。
入力
入力は、2 行から成る。1 行目には、数列の長さN(1 <= N <= 1000) が書かれている。2 行目には、数列の各
要素が、空白区切りで書かれている。各要素は、0 以上 10000 以下である。
出力
最長の「順序付けられた部分列」の長さを表す1 つの整数を出力せよ。
入力の例
7 1 7 3 5 9 4 8
出力の例
4
出典
Central Europe 1995