[AtCoder] ABC 134 E – Sequence Decomposing

問題

方針

広義単調減少部分列

\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言えるので、最長増加部分列を求めるようにして求めます。

コード