No.127

以下のように定める.

左端が $i$, 右端が $j$ 以下の範囲での左端から数えた最長門松もどきを $A(i, j)$

右端が $i$, 左端が $j$ 以上の範囲での右端から数えた最長門松もどきを $B(i, j)$

このとき,

$$\begin{eqnarray} A(i, j) = \begin{cases} 1 & (i = j) \\ A(i+1, j) & (A_i \geq A_j) \\ \max(A(i+1, j), B(j, i+1) + 1) & (otherwise) \end{cases} \end{eqnarray}$$

となる. $B(i, j)$ も同様である.

メモ化再帰を使って $\max(A(0, n-1), A(1, n-1), \dots, A(n-1, n-1), B(n-1, 0), B(n-2, 0), \dots, B(0, 0))$ を求める.