配列をソートするための最小操作数

Question

私はthisの問題を解決しようとしていますが、正しいアプローチを思いついていません。 問題を解決するための正しい解決策は何ですか？

Answer 1

O（n log n）（配列をソートすることによって）で実行できる最長の連続した部分シーケンスが見つかるはずです。その後、必要な変更の数はN - longest consecutive increasing subsequenceです。連続することによって、並べ替えられた配列内に順序があることに注意してください。

例えば：

1 7 6 2 3 4 5 => 1-2-3必要な移動の 数は4

1 6 3 4 5 2であり、最長の連続増加サブシーケンスであります7 => 1-2または4-5または6-7は、最長連続増加 サブシーケンスである、1-4-5-7が最長増加サブシーケンスであるが、必要な移動の 数は5ない3

であることに注意

なぜこの作品：

ベストアルゴリズムは、項目の場所のいくつか、Xとして変更することなく最大のサブシーケンスを呼び出し、あなたが作業中に互いに関連X項目の位置を変更する文句を言わないので、彼らは増加モードでソートする必要がありますを変更しません。しかし、配列の最初または最後の項目を移動することが許可されているだけなので、Xの項目の間に項目を置くことはできません（Xは操作中に最大の変更されていない部分列です）。したがって、Xアイテム。並べ替えられ、ソートされた形式で連続している必要があります。

必要な変更の数はN- length of Xより小さくすることはできませんが、N-length of X operationで仕事をするのは難しくありません。