题目大意
给定一个长度为n的整数数列A，要求修改其中尽可能少的数，使得整个数列变成一个不下降数列，即A1 ≤ A2 ≤ A3 ≤ … ≤ An。
题目分析
数列问题一直是面试题当中比较热门的类型之一，原因是它不需涉及过多复杂的数据结构，可以更直观地考察候选人的算法设计能力。对于这个问题来说，我们最关心的实际上只有两点：
1. 修改哪些数字；
2. 怎样对数字进行修改。
下面我们将围绕这两个子问题进行讨论。如果把数列A用直观的折线图表现出来的话，可以变成类似于下图这种形状：
对于我们来说，需要做的就是修改尽可能少的点的位置，使得整个折线是单调不下降的，如下所示：
容易发现，要让修改的数字尽可能少，事实上就是让整个数列保留的数字尽可能多（显然这两者是等价的）。而保留下来的子序列是最后整个序列的一部分，因此它也必须满足不下降的性质。因此，我们所需要保留的实际上就是数列A的最长不下降序列！
而对于需要修改的数字，一个简单的修改方法就是，直接把它变成离它最近的最长不下降序列元素即可，如下所示：
所以我们就得到了这个问题的解法：
1. 求解A的最长不下降序列Sub(A)；
2. 对于在Sub(A)中的元素，保持不变；
3. 对于不在Sub(A)中的元素，把它变成离它最近的Sub(A)中的元素即可。
最长不下降序列是动态规划的经典问题。令dp[i]表示以A[i]作为末尾的最长不下降序列。显然，dp[i]要么等于1（序列只包含A[i]这个数），要么必然存在A[j]（1 ≤ j < i）作为这个序列中A[i]之前的最后一位，那么以A[i]结尾的最长不下降序列的长度，就等于以A[j]结尾的最长不下降序列的长度 + 1。由于j < i，为了保持不下降的性质，这里还必须满足A[j] ≤ A[i]。于是我们可以得到状态转移方程：
dp[i] = Max{dp[j] + 1} (0 ≤ j < i, A[j] ≤ A[i])
dp[0] = 0
整个序列的最长不下降序列的长度就是dp[i]中的最大值。一个简单的O(n * n)的实现方式如下：
问题分析到这里其实已经被完整地解决了，但仍然有优化的空间。事实上，计算最长不下降序列可以有更快的方法。上述代码的复杂度瓶颈在于，当我们求dp[i]的时候，需要一个从1到i - 1的扫描来找到最大的dp[j]进行更新，因此状态转移的复杂度是O(n)的。如果维护一个单调栈或者使用线段树，可以将取最值的操作复杂度下降为O(logn)，从而将总的时间复杂度降为O(nlogn)。限于篇幅，这里就不详细展开了。
回顾这个问题，我们实际上将它做了一个对称处理（修改最少 -> 保留最多），从而成功地把它抽象成了一个经典的最长不下降序列问题。但这只解决了开篇时我们提出的两个子问题的其中一个（修改哪些数字），而对于另一个子问题（如何修改它们），我们采用的方法是让它们保持和前一个数字一致即可。而如果这个问题修改成下面这个版本，还能不能用类似的方法来解决？
给定一个长度为n的整数数列A，要求修改其中尽可能少的数，使得整个数列变成一个单调上升数列，即A1 < A2 < A3 < … < An。
这个题目的具体解法，我们会在之后的文章中讨论。
作者：szefany@算法号