如@sfx所述,这等同于寻找最长的非降子序列。
如果您在输入数组A中找到任何非降子序列S,则只需要更改A中其余元素的值即可使整个数组成为非降序列。需要更改的元素数量为|A| - |S|。
如果该子序列是最长的非降子序列,即给出了已经排序的最大元素数量,则要更改的元素数量|A| - |S|将被最小化。如果选择任何较短的非降子序列,则需要更改更多的元素。
您可以使用耐心排序来找到此子序列的长度。
维基百科上的算法:
使用您的示例3:
[9, 11, 5, 7]
插入 [9]:
[9]
插入[11]: 输出数组中不存在大于或等于[11]的值,因此需要添加另一个栈:
[9, 11]
插入 [5]:第一个大于或等于 [5] 的值是 [9],因此替换 [9]:
[5, 11]
插入 [7]: 第一个大于或等于 [7] 的值是 [11],替换 [11]:
[5, 7]
输出数组的长度是最长非降子序列的长度。使整个序列非降所需的操作次数等于输入数组元素数量减去此子序列的长度。
使用二分查找确定下一个值应放置的位置,此方法的最坏时间复杂度为 O(n log n)。
您可以在这里找到有关正确性的讨论和参考文献:为什么耐心排序能找到最长递增子序列?
我认为这个问题等价于在序列中找到最长的非递减链。
将每个索引i视为图的节点。那么当且仅当i<j且L[i]≤L[j]时,节点i向节点j有一个箭头。然后使用图论技术查找图中的最长路径。
由于条件i<j,因此不会出现循环。