这个问题等同于最长增长的子序列问题。
您将必须定义一个比较运算符
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]); } }}我希望这段代码可以使我的答案更加清楚。
