最長増加部分列 Python3編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A = a_1, ..., a_N が与えられます。
この数列の単調増加な (連続でなくても良い) 部分列の最長の長さを出力してください。
長さ L の数列 B = b_1, b_2, ..., b_L において b_{i-1} < b_i (2 ≤ i ≤ L) が成り立つならば、B は単調増加な数列です。
例えば 1, 2, 3, 4 や 1 は単調増加な数列ですが、4, 3, 2, 1 や 1, 1, 1 は単調増加な数列ではありません。
- 入力される値
-
N
a_1 a_2 ... a_N
・1 行目に数列の長さ N が与えられます。
・2 行目に数列 A の要素 a_1, a_2, ..., a_N が空白区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします
・入力はすべて整数
・1 ≦ N ≦ 1,000
・1 ≦ a_i ≦ 1,000 (1 ≦ i ≦ N)
- 入力例1
-
8
1 1 2 2 3 3 4 4
- 出力例1
-
4
- 入力例2
-
9
1 2 1 3 1 4 1 5 1
- 出力例2
-
5
