您应该找到最长的连续增加子序列,可以在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是增长最长的子序列,但所需的移动次数是5而不是3.
为什么这样有效:
最佳算法不会更改某些项目的位置,调用最大的子序列而不进行更改,因为在操作期间X不会更改X彼此相关的项目的位置,因此它们应按增加模式排序.但是因为你只是允许在数组的第一个或最后一个中移动一些项目,你不能在项目之间放置任何X项目(注意我们假设X在操作期间最大的未更改的子序列),所以X项目之间应该没有间隙.因此它们应按排序格式排序和连续.
因此,所需的更改次数不能小于N- length of X,但也不难做到N-length of X operation.