ARC140 C - ABS Permutation (LIS ver.) (500)
隣接する2要素間の差の絶対値がどんどんと大きくなるようにしたい
最初の1個を無視すると、ある値$ A,$ A-1,$ A+1,$ A-2,...のようにしていくのが良い
上下は逆に初めても良い
この$ Aを全探索して最長になるものを求める
実際に全部を試すと$ O(N^2)になるので計算量を落とす必要がある
自身の下の要素の個数と、上の要素の個数からいくつ上の配列が作れるかは$ \mathcal{O}(1)計算できる
少ない方の個数の2倍、またはそれに+1になる
最終結果は配列を出力する必要があるので実際に配列を計算する必要がある