对数组进行排序所需的最少操作数

我正在尝试练习解决 Codeforces 中的问题。它通过将数组的元素移动到数组的开头或结尾来对数组进行排序。起初我认为它是最长的递增子序列，但在某些情况下它不起作用。例如，如果输入是 4,1,2,5,3，则 LIS 是 3，但问题的答案是将 4 移动到数组的末尾，然后将 5 移动到数组的末尾，这给了我们 2。正在尝试此 LIS 中的示例 1,6,4,5,9,8,7,3,2 是 1,4,5,9 但问题的答案是 1 和 2 之间的 7 个移动。我得到知道我应该使用贪婪的方法，但不太能理解。有人可以帮我吗？

我们可以看到，要对数组进行排序，只需移动每个元素即可at most one.

因此，为了最小化移动次数，我们需要找到未移动的元素的最大数量。这些元素是最长连续序列，这是序列(a0, a1, ... an) with a(i + 1) = ai + 1.

例如，

(4,1,2,5,3)，最长连续序列为(1,2,3)

(5,2,1,3,4)，最长连续序列是(2,3,4)

所以我们有我们的代码：

int[]longest = new int[n + 1];
int result = 0;
for(int i = 0; i < n; i++){
    longest[data[i]] = longest[data[i] - 1] + 1;
    result = max (longest[data[i]] , result);
}

print "Minimum number of move is " + (n - result)

解释：

在代码中，我使用了一个数组longest哪个索引ith存储最长的连续序列，结束于value i.

所以，我们可以看到longest[i] = longest[i - 1] + 1.

最长连续序列的结果是存储在中的最大值longest array.