こんにちは、ゆーてぃーです。今回は「ゆーてぃーのAtCoder精進【21日目】」ということで、2024年12月21日に行われたABC385のC問題を解きたいと思います。

問題

C - Illuminate Buildings

$N$ 棟のビルが等間隔に一列に並んでいます。手前から $i$ 番目のビルの高さは $H_i$ です。

あなたは次の条件をともに満たすようにいくつかのビルを選んで電飾で飾ろうとしています。

最大でいくつのビルを選ぶことができますか？　なお、ちょうど1 つのビルを選んだときは条件を満たすとみなします。

入力は以下の形式で標準入力から与えられる。

$N$

$H_1\ ...\ H_N$

答えを出力せよ。

$N$ が小さいので全探索をします。具体的には $1 \sim \frac{N}{2}+1$ の間隔を保ち、開始地点をずらして調べていきます。同じ高さが続いていたらカウントを増やし、異なる高さになったらカウントを0にして再開します。カウントの最大値が答えになります。

計算量が[O (N ^ 3)]くらいになると思いましたが実装してみたら[O (N²)]くらいになったので助かりました。