这个问题等同于最长增长的子序列问题。

您将必须定义一个比较运算符less。less(a, b)将true且仅当在目标序列中a之前时才返回b。现在，使用此比较运算符，计算源序列的最大递增子序列。您将不得不移动不属于该子序列的每个元素（否则该子序列将不会达到最大值），并且只能将其精确移动一次（将其移动到目标位置）。

编辑：按照阿米特的要求，这里是我对上述声明的证明：让我们表示目标序列B，让我们表示源序列A。令n = |A|和k为上述最长的递增序列的长度。

• 假设移动B距离A比少即可n - k。这意味着至少不会移动中的n - k + 1元素A。令s 1，s 2，… s m为不移动的元素集。从这个假设我们知道m > k。现在，由于这些元素尚未移动，因此它们相对于彼此的相对位置无法更改。因此，所有这些元素在目标序列中的相对位置与B中的相同A。因此，对于任何一个，上面定义的运算符less（s i，s j）应该是正确的。但是，如果这是真的，则s 1，si``j在图2中，… s m是递增序列，因为m > k这导致与k是最长递增序列的长度的假设相矛盾。
• 现在，让我们展示的算法，以达到B从A移动的所有元素，但属于最长递增序列的一部分的人。我们将按照它们在B中出现的顺序移动元素。我们将不移动属于最长递增序列的元素。如果当前元素是B中的第一个元素，我们只需将其移到序列的开头即可。否则，我们将当前元素移动到B中前一个元素的位置 之后 。请注意，此元素可以是我们已移动的前一个元素，也可以是最长增长顺序中的一个元素。请注意，在每一步中，当我们要移动带有index的元素时i，所有带有index的元素1, 2, ...i-1已经相对于彼此具有正确的相对位置。

编辑：添加一些代码，使答案更清晰。我没有javascript方面的专家，因此可以随时纠正或批评我的解决方案。

让我们定义一个带有transform(a, s)两个参数的函数-
如语句中所述列出a和b。首先，我将创建一个映射positions，将每个元素映射a到其在s中的位置：

var positions = {};
for (var i = 0; i < a.length; ++i) {
  positions[a[i]] = i;
}

现在，有了这个数组，我可以定义一个辅助函数，而不必像上面的答案中所述。更不会取两个值a和b（和辅助地图我刚刚创建）和返回，如果属实且仅当a是之前b在s（目标列表）：

function less(a, b, positions) {
  return positions[a] < positions[b];
}

现在，我将不描述如何a针对该比较运算符找到最大的递增子序列。您可以查看此问题以获取详细说明。我只是假设我定义了一个函数：

function max_increasing_subsequence(a, positions)

a相对于less上面定义的比较运算符（使用positions）作为列表返回最大的递增子序列。我将使用您的第二个示例来说明到目前为止我们所拥有的：

A = [9,1,2,3,0]
S = [0,1,2,3,9]

位置值如下：

positions = { 0 : 0,
              1 : 1,
              2 : 2,
              3 : 3,
              9 : 4}

的结果max_increasing_subsequence(a, positions)将是[1, 2, 3]。顺便说一句，如果其中可能包含重复元素，a则返回索引而不是返回元素可能更好max_increasing_subsequence（在此特定示例中，差异将不可见）。

现在，我将创建另一个助手映射，以指示最大递增子序列中包含哪些元素：

var included = {};
l = max_increasing_subsequence(a, positions);
for (var i = 0; i < l.length; ++i) {
  included[l[i]] = true;
}

现在，您可以通过进行一次迭代来完成解决方案s。我将为最后一个元素添加一个特殊情况，以使代码更易于理解：

if (!(s[s.length - 1] in included)) {
  console.log("Move" + s[s.length - 1] + " at the end");
}
for (var i = s.length - 2; i >= 0; --i) {
  if (!(s[i] in included)) {
    console.log("Move" + s[i] + " before " + s[i + 1]);
  }
}

请注意，在上面的解决方案中，我假设每次您记录一个新命令时，a都将在执行所有先前命令后立即就阵列的顺序记录该命令。

因此，总的来说，我相信transform应该看起来像这样：

function transform(a, s) {
  var positions = {};
  for (var i = 0; i < a.length; ++i) {
    positions[a[i]] = i;
  }
  var included = {};
  l = max_increasing_subsequence(a, positions);
  var included = {};
  for (var i = 0; i < l.length; ++i) {
    included[l[i]] = true;
  }
  if (!(s[s.length - 1] in included)) {
    console.log("Move" + s[s.length - 1] + " at the end");
  }
  for (var i = s.length - 2; i >= 0; --i) { // note s.length - 2 - don't process last element
    if (!(s[i] in included)) {
      console.log("Move" + s[i] + " before " + s[i + 1]);
    }
  }
}

我希望这段代码可以使我的答案更加清楚。