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