【連続列】最長減少連続部分列
(paizaランク B 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, ... , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≧ a_{i+1} が成り立っているとき、区間 [l, r] は逆背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
逆背の順であるような区間のうち、最長であるものの長さを出力してください。
- 入力される値
-
n
a_1
a_2
...
a_n・ 1行目に、横一列に並んでいる人の人数 n が与えられます。
・ 続く n 行のうち i 行目では、人 i の身長 a_i が与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
逆背の順であるような区間のうち、最長であるものの長さを出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ n ≦ 200,000
・ 100 ≦ a_i ≦ 200
- 入力例1
-
5
187
192
115
108
109
- 出力例1
-
3
