問題概要
長さ 
の数列 
が与えられる. このとき好きな回数だけ(0回でも)以下の操作のいずれかを行い, 新たに数列 
を作る:
- の要素のうち最も左の要素を の末尾に追加し, からその要素を削除する.
- の要素のうち最も右の要素を の末尾に追加し, からその要素を削除する.
このようにして作る を狭義単調増加になるようにつくるとき, の最大の長さは？(操作列も作る)
問題へのリンク
制約
解法
のようにカーソルを置いて, 
を右へ, 
を左に動かしていく感じで毎回 
のどちらかを取るかを選択することにします.
まず, 
なら話は簡単で, とれるなら小さい方, とれないなら大きい方, どっちも取れないならおしまいです. 
にもかかわらず 
をとると, 
をとれたのにこれ以降取れなくなってしまい得られる数列が最大ではなくなってしまいます.
問題は 
の時ですが, このとき選択しなかったほうはこれ以降選択することができなくなります(狭義単調増加になるようにとらなければならないので). よって, これ以降左からしかとらないパターンと, 右からしかとらないパターンを両方ためして長い方を採用すれば良いです.
実装
可読性, おしまい
Submission #145094706 - Codeforces
