操作中のどの瞬間も、数列 \(X\) とスタック \(S\) の中身は単調であることがわかります（細かい議論は省略）

途中まで操作をした状態「\(a_l\) に対する操作を行う直前の時点で、\(X\) の末尾の値は \(d\) であり、\(S\) の先頭の値は \(u\)」から続けて操作を行うことを考えてみます。\(u\) をpopするのが \(a_r\) に対する操作を行う直前である 場合、\(a_l,\ldots,a_{r-1}\) に対する操作においては

• \(d\) 未満の値を \(X\) に追加することはできない
• \(u\) より大きな値を \(S\) に追加することはできない

という条件を満たしながら、最長の単調増加列を作ることになります。

以上までの考察を踏まえて \(f(l,r,d,u)\) を 「\(a_l,\ldots,a_{r-1}\) に対して操作を行い作ることができる、\(d\) 以上 \(u\) 以下の値からなる最長の単調増加列の長さ」とします。\(f(l,r,d,u)\) は次の情報から計算することができます。

• \(a_l\) を使わない場合
  \(f(l+1,r,d,u)\)
• \(a_l\) を \(X\) に追加する場合
  \(1+f(l+1,r,a_l,u)\)
• \(a_l\) を \(S\) に追加する場合
  \(a_l\) を\(a_k\) の操作直前にpopするとすれば \(1+f(l+1,k,d,a_l)+f(k,r,a_l,u)\)

元の問題の答えは \(f(1,N+1,1,50)\) です。この計算は状態数が \(O(N^2A^2)\)、遷移が \(O(N)\) のメモ化再帰により行うことができるので \(O(N^3A^2)\) の計算量になり、十分高速に動作します。

実装例(C)