技術室奥プログラミングコンテスト#4 Day1：D - スキップ

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d

解法

まず，要素が重複している連続する区間は 1 つの要素にまとめてしまってよい．なぜならば，このような区間でどこをスキップしてもスコアは増えないから．こうすることによって，全ての区間で単調増加 or 単調減少となる．1 つの単調増加 or 単調減少列において，端である 2 つのみを選んだ時と要素の中（端以外）を追加で選んでも，得られるポイントは変わらない．なので，数列中に登場する単調増加 or 単調減少列の端を選んでいくのが最適になる．これは，増加と減少の切り替わるところを判定しながら前から数列を見ていくことで処理できる．O(N)．