我正在尝试解决一个难题，但恐怕遇到了障碍 - 我不知道如何解决它。我想也许这里有人偶然发现了类似的东西，如果没有，我相信那些喜欢制作算法的人会喜欢尝试找到解决方案：
我们得到一个未排序的数组。我们可以进行以下两种移动之一：从数组中取出任何元素并将其移动到数组的开头或末尾。我们还给出了数组最终应该是什么样子。我们应该用最少的步数对数组进行排序。
例子：
5 1 4 3 2 - > starting array
3 1 2 5 4 - > target array
Steps: move 5 to the end 1 4 3 2 5
move 3 to the beginning 3 1 4 2 5
move 4 to the end 3 1 2 5 4
已达到目标数组，最少步数为 3。
有谁知道如何解决这个问题？
我相信诀窍是找到两个数组之间的最长公共子序列（您可以在 O(n^2) 时间内找到它。这将为您提供最大可能的不必移动的数字集，相反，必须移动的最小可能数字集。一旦有了必须移动的数字集，弄清楚如何移动它们应该是相当简单的。
在你的例子中：
(5, 1, 4, 3, 2) 和 (3, 1, 2, 5, 4) 之间的最长公共子序列是 (1, 4), (1, 2), (3, 2) 或 (5 ，4）。每个子序列都会告诉您最小移动次数是 3（显然，您选择的移动次数会有所不同）。
编辑
我认为这基本上是正确的答案（沃恩做了一些修改）。
首先，我们像往常一样构建最长公共子序列问题的子序列长度数组（M[i][j] = 以 source[i] 和 target[j] 结尾的最长公共子序列的长度）。
然后，我们不再选择解决方案，而是枚举所有可能的最长公共子序列。
然后，我们为每个子序列分配一个分数，该分数是目标序列中最长连续块的长度。
在示例中，我们得到：
(1, 2) - 得分 2 (1, 4) - 得分 1 (3, 2) - 得分 1 (5, 4) - 得分 2
我们选择任何得分最高的序列，并生成适当的移动指令，以移动该序列之前或之后的剩余数字。