060 - Chimera（★5）
$ L[i] = i
番目を最後にした時の先頭から
$ i
番目までのLISの長さ
$ R[i] = i
番目を先頭にした時の末尾から
$ i
番目までのLDSの長さ
を求めておく。これはSegment Tree上のDPで可能。要素の小さい順に見ていき、「そこより左の最大値+1」と更新する。
求める値は
$ \max L[i]+R[i]-1
と表せる。
https://atcoder.jp/contests/typical90/submissions/60137221
要は門松