\(B\) と一致する \(A\) の部分列がない場合は答えは No です。以降では、そうではない場合を考えます。

\(B\) と一致する \(A\) の部分列であって、取り出す位置の列が辞書順最小になるものと最大になるものをそれぞれ求めます。両者が異なるとき、またそのときに限って \(B\) と一致する \(A\) の部分列は \(2\) つ以上あります。

取り出す位置の列が辞書順最小、最大となる部分列は、それぞれ \(A\) を前、後ろから走査する貪欲法によって \(\mathrm{O}(N)\) 時間で求めることができます。