明らかに \(X\) は広義単調増加にするべきです。本解説では暗黙に \(X\) は広義単調増加であるものとします。
まず、最終的に \(X\) に含まれない整数は \(S\) に移動させずに捨てると仮定して良いです。この仮定の下では最終的に \(S\) は空になるはずで、また、\(S\) の先頭に移動させされる整数はその時点で \(S\) に含まれるどの整数よりも小さくない必要があります。特に、最終的に \(X\) に含まれる整数の最大値 \(M\) を初めて \(S\) に移動させる時、\(S\) は空である必要があります。
以上を踏まえて次のような \(\mathrm {dp}\) を考えます。

• \(\mathrm {dp}_{i,j,k,l}\) : \(a_i,a_{i+1},\ldots,a_j\) のうち \(k\) 以上 \(l\) 以下のものを用いて \(X\) を作る場合のスコアの最大値

本問の答えは \(\mathrm{dp}_{1,N,1,50}\) です。
遷移を考えます。

\(l\) が最終的な \(X\) に含まれない場合の遷移

\(\mathrm {dp}_{i,j,k,l-1}\) が対応します。

\(l\) が最終的な \(X\) に含まれる場合の遷移

\(a_m=l\) となる箇所それぞれについて、そこが \(l\) を初めて \(S\) に移動させる箇所であるという仮定に基づいた遷移を行います。先述の通り、この時点で \(S\) は空である必要があります。また、最終的に \(X\) に含まれる \(a_m\) より前の項のうち最大値を \(n\) とすると、\(a_m\) より後においては \(n\) より小さな整数を \(X\) に含めることが出来ません。(\(S\) が空なので \(n\) は既に \(X\) の末尾にあることに注意してください)
逆に、\(a_m\) より前で作られる \(X\) を \(X_1\)、 \(a_m\) より後で(\(n\) より小さな整数を含めずに)作られる \(X\) を \(X_2\) とした時、\(a_m,X_1,X_2\) を合わせた \(1+|X_1|+|X_2|\) 項の \(X\) を作ることが出来ます。よって、\(\mathrm{dp}_{i,j,k,l} = \underset{k \leq n \lt l}{\max}(1 + \mathrm{dp}_{i,m-1,k,n} + \mathrm{dp}_{m+1,j,n,l})\) という遷移が正当です。(なお、\(m\) が \(a_m=l\) となる最初の位置という話の流れに沿って \(n\) の範囲に \(l\) を含めていませんが、含めてしまっても問題ありません)
計算量の解析を行います。以降、\(a_i\) の最大値が \(N\) に等しいものとします。(仮にそうでなかった場合も座標圧縮をすれば \(N\) に揃えることが出来ます) \(\mathrm{dp}\) の状態数は \(\mathrm{O}(N^4)\) で、普通に実装をするとそれぞれに対して\(a_m=l\) となる場所を探す処理をすることになるのでまずその部分が \(\mathrm{O}(N^5)\) となります。また、\(a_m=l\) となる箇所ごとに \(n\) をすべて調べる、という部分で \(\mathrm{O}(N)\) の遷移が発生します。これは、\((i,j,k)\) それぞれに対して \(l=a_i,l=a_{i+1},\ldots,l=a_{j}\) となる場合に発生するので結局計算量は全体で \(\mathrm{O}(N^5)\) となります。この多項式に直接値を代入すると \(50^5=312500000\) となり \(2\) 秒の実行時間制限に対して値が大きいように思われますが、定数倍が軽いので十分高速です。また、方針によっては \(\mathrm{O}(N^6)\) になりますが、定数倍に気を付ければそれでも間に合うかもしれません。