最長増加連続部分列 VB(Beta)編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

長さ N の数列 A = a_1, a_2, ..., 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 ≦ 10^6
・1 ≦ a_i ≦ 1,000 (1 ≦ i ≦ N)

入力例1: 8
1 2 3 1 2 3 4 5

出力例1: 5

入力例2: 5
1 1 1 1 1

出力例2: 1

問題一覧へ戻る