2.16　求数组中最长递增子序列

写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。

例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。

分析与解法

根据题目的要求，求一维数组中的最长递增子序列，也就是找一个标号的序列b[0]，b[1]，…，b[m]（0＜＝b[0]＜b[1]＜…＜b[m]＜N），使得array[b[0]]＜array[b[1]]＜…＜array[b[m]]。

【解法一】

根据无后效性的定义我们知道，将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态来说，它以前各阶段的状态无法直接影响它未来的决策，而只能间接地通过当前的这个状态来影响。换句话说，每个状态都是过去历史的一个完整总结。

同样地，仍以序列1，-1，2，-3，4，-5，6，-7为例，我们在找到4之后，并不关心4之前的两个值具体是怎样，因为它对找到6并没有直接影响。因此，这个问题满足无后效性，可以使用动态规划来解决。

可以通过数字的规律来分析目标串：1，-1，2，-3，4，-5，6，-7。

使用i来表示当前遍历的位置：

当i＝1时，显然，最长的递增序列为（1），序列长度为1。

当i＝2时，由于-1＜1。因此，必须丢弃第一个值然后重新建立串。当前的递增序列为（-1），长度为1。

当i＝3时，由于2＞1，2＞-1。因此，最长的递增序列为（1，2），（-1，2），长度为2。在这里，2前面是1还是-1对求出后面的递增序列没有直接影响。

依此类推之后，可以得出如下的结论：

假设在目标数组array[]的前i个元素中，最长递增子序列的长度为LIS[i]。那么，

LIS[i＋1]＝max{1，LIS[k]＋1}，array[i＋1]＞array[k]，for any k＜＝i

即如果array[i＋1]大于array[k]，那么第i＋1个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列。与此同时array[i＋1]本身至少可以构成一个长度为1的子序列。

根据上面的分析，就可以得到如下代码：

代码清单2-31　C#代码

这种方法的时间复杂度为O（N²＋N）＝O（N²）。

【解法二】

显然，O（N²）的算法只是一个比较基本的解法，我们需要想想看是否能够进一步提高效率。在前面的分析中，当考察第i＋1个元素的时候，我们是不考虑前面i个元素的分布情况的。现在我们从另一个角度分析，即当考察第i＋1个元素的时候考虑前面i个元素的情况。

对于前面i个元素的任何一个递增子序列，如果这个子序列的最大的元素比array[i＋1]小，那么就可以将array[i＋1]加在这个子序列后面，构成一个新的递增子序列。

比如当i＝4的时候，目标序列为：1，-1，2，-3，4，-5，6，-7最长递增序列为：（1，2），（-1，2）。

那么，只要4＞2，就可以把4直接增加到前面的子序列中形成一个新的递增子序列。

因此，我们希望找到前i个元素中的一个递增子序列，使得这个递增子序列的最大的元素比array[i＋1]小，且长度尽量地长。这样将array[i＋1]加在该递增子序列后，便可找到以array[i＋1]为最大元素的最长递增子序列。

仍然假设在数组的前i个元素中，以array[i]为最大元素的最长递增子序列的长度为LIS[i]。

同时，假设：

长度为1的递增子序列最大元素的最小值为MaxV[1]；

长度为2的递增子序列最大元素的最小值为MaxV[2]；

……

长度为LIS[i]的递增子序列最大元素的最小值为MaxV[LIS[i]]。

假如维护了这些值，那么，在算法中就可以利用相关的信息来减少判断的次数。

具体算法实现如下：

代码清单2-32　C#代码

由于上述解法中的穷举遍历，时间复杂度仍然为O（N²）。

【解法三】

解法二的结果似乎仍然不能让人满意。我们是否把递增序列中间的关系全部挖掘出来了呢？再分析一下临时存储下来的最长递增序列信息。

在递增序列中，如果i＜j，那么就会有MaxV[i]＜MaxV[j]。如果出现MaxV[j]＜MaxV[i]的情况，则跟定义矛盾，为什么？

因此，根据这样单调递增的关系，可以将上面方法中的穷举部分进行如下修改：

如果把上述的查询部分利用二分搜索进行加速，那么就可以把时间复杂度降为O（N*log₂N）。

小结

从上面的分析中可以看出我们先提出一个最直接（或者说最简单）的解法，然后从这个最简单解法来看是否有提升的空间，进而一步一步地挖掘解法中的潜力，从而减少解法的时间复杂度。

在实际的面试中，这样的方法同样有效。因为面试者更加看中的是应聘者是否有解决问题的思路，不会因为最后没有达到最优算法而简单地给予否定。应聘者也可以先提出简单的办法，以此投石问路，看看面试者是否会有进一步的提示。