【部分列】最長減少部分列
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
n 本の木が横一列に並んでいます。左から i 番目の木を木 i と呼ぶことにします。木 i の高さは a_i [cm] です。
あなたは、何本かの木を伐採することによって、残った木を左から順に見ると高さが単調減少になっているようにしたいと考えています。つまり、残った木を左から 木 k_1, 木 k_2, ... , 木 k_m とすると、a_{k_1} > a_{k_2} > ... > a_{k_m} が満たされているようにしたいです。なるべく多くの木が残るように工夫して伐採する木を選んだとき、伐採されずに残る木の本数が最大でいくつになるか求めてください。
なお、最初から n 本の木が単調減少に並んでいる場合は、1本も伐採しなくてよいものとします。
- 入力される値
-
n
a_1
a_2
...
a_n・ 1行目に、横一列に並んでいる木の本数 n が与えられます。
・ 続く n 行のうち i 行目では、木 i の高さ a_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
残った木を左から見ると高さが単調減少になっているように木を伐採したとき、伐採されずに残る木の本数の最大値を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 5,000
・ 1 ≦ a_i ≦ 1,000,000,000
・ a_i ≠ a_j (i ≠ j)
- 入力例1
-
5
109
110
108
103
100
- 出力例1
-
4
