yukicoder No.209 Longest Mountain Subsequence

DP★3．3ヶ月位前にも一度挑戦していて，その時は自分の方針のアラが探せず出来ずじまいだったが，今回は一発でACできた．

方針： ${S_{i-1}-S_{i-2} \lt S_i-S_{i-1}}$ を満たす最長の上昇部分列の長さを今選んでいる要素のindex，直前に選んだ要素のindexの情報を持った上で求める．下は $A= \left\{1,7,5,3,1,6,3,9,1 \right\}$ のときの例．各 $i$ に対する最大値が $A_i$ を最後に使ったときの最長の上昇部分列長である．自分の提出は左からの上昇列長を求めたら，Aを反転して同一の処理をしている．