以下のアルゴリズムで答えを求めることができます。

• 空の配列 \(ans\) を用意する
• \(i=1,\ldots,N\) の順で以下を繰り返す
  • \(A_i\) がすでに \(ans\) の中にあれば何もしない
  • \(A_i\) がまだ \(ans\) の中にないとき以下を行う
    • 「\(ans\) の末尾の要素が \(A_i\) より大きく、かつ、その値が \(A\) の中で \(i\) 番目以降にもまだ登場するなら取り除く」を行えるだけ行う
    • その後、\(ans\) の末尾に \(A_i\) を追加する

各値がansの中にあるかどうかと、各値が \(A\) の中で最も後ろにある位置がわかっていれば、これらの操作は \(A\) の要素1つあたりならし \(O(1)\) ででき全体で \(O(N)\) になります。

実装例(C++)

正当性は、\(i\) のループのどの時点においてもansが「『\((A_1,\ldots,A_i)\) の部分列であって、\((A_{i+1},\ldots,A_N)\) の適切な部分列と連結することで \((1,\ldots,M)\) の並び替えにできるような極大なもの』のうち辞書順最小」であることが \(i\) に関する帰納法により示せることからわかります（\(i\) まで処理した時点でできる列の末尾が \(A_i\) であるなら、\(A_i\) を取り除いた列は \(i-1\) のときの列のprefix になり、末尾が \(A_i\) でないなら \(i-1\) のときの列に一致します）