私はspojでこの問題を試してきましたが、正しいアプローチを思い付くことができませんでした。問題を解決するための正しいアルゴリズムは何ですか?
1 に答える
O(n log n)で(配列をソートすることにより)実行できる最長連続増加部分列を見つける必要があります。その後、必要な変更の数はですN - longest consecutive increasing subsequence
。連続とは、ソートされた配列に順序があることを意味することに注意してください。
例えば:
1 7 6 2 5 4 3 => 1-2-3は最長連続増加部分列であり、必要な移動数は4です。
1 6 4 3 5 2 7 => 1-2または4-5または6-7は最長連続増加部分列であり、1-4-5-7は最長増加部分列ですが、必要な移動数は3ではなく5であることに注意してください。
これが機能する理由:
最良のアルゴリズムは、アイテムの場所の一部を変更せず、変更なしで最大のサブシーケンスを呼び出します。操作中に相互に関連するアイテムX
の位置を変更しないため、増加モードで並べ替える必要があります。X
ただし、配列の最初または最後にいくつかのアイテムを移動することを許可したため、アイテム間にX
アイテムを配置することはできません(操作中に変更されない最大のサブシーケンスであると想定していることに注意してくださいX
)。したがって、アイテム間にギャップはありませんX
。したがって、それらはソートされ、ソートされた形式で連続している必要があります。
したがって、必要な変更の数は、より少なくすることはできませんがN- length of X
、で作業を行うのも難しくありませんN-length of X operation
。