DESCRIPTION: 数组的最长递增子序列(LIS) Given a sequence of n real numbers a1, ..., an, determine a subsequence (not necessarily contiguous) of maximum length in which thevalues in the sub- sequence form a strictly increasing sequence. 这是一个动态规划的问题,个人觉得DP最关键的是首先写出问题的子问题空间, 遵循的原则如下,(参考自算法导论) 子问题空间越简单越好,必要的时候才进行扩充。 本人打算专门写一篇blog关于自己选择子问题空间的一些经验。
Definition: (定义非常关键,数学证明中,首先必须非常清楚定义,而且有的时候好的简单的对子问题空间的定义,有利于构造高效的算法) array[1-length] 输入数组 LIS[1-length] 前i个元素中以array[i]为最大元素的最长递增子序列(LIS)的长度 (还可以有第二种定义:前i个元素中的最长递增子序列的长度, 注意,这个定义,并不一定要求以array[i]为最大元素) 算法1: LIS若采用第一种定义: 前i个元素中以array[i]为最大元素的最长递增子序列(LIS)的长度 算法非常直接,递推关系式如下 LIS[i+1]= max{LIS[i-k] + 1}, array[k] < array[i+1], for any k <=i 意思是: 以array[i+1]为最大元素的LIS,的倒数第二个元素array[k],可以选择那些array[i+1]前面的,并且值小于array[i+1]的元素。 很容易证明,满足最优子结构。 注意:最优值并不一定在 LIS[N]取得,因为现在 LIS[i]表示的是前i个元素中以array[i]为最大元素的LIS,所以 OPT = MAX(L[i]]) 复杂度: N个子问题,每个子问题计算耗时O(N), 最后找最大值O(N) So, complexity = O(N^2) + O(N) = O(N^2)
算法2:(错误的算法) LIS若采用第二种定义:前i个元素中的最长递增子序列的长度。 这种定义有一个好处,最优值就是LIS[N]。因为,LIS[i+1]至少应该比LIS[i]一样好。。 所以LIS[]这个数组一定是非递减的。。 在算法1递推关系式的基础上,加上LIS[i+1与L[i]取max即可] 但是, LIS[i+1] =max{LIS[i], max{LIS[i-k] + 1}, array[k] < array[i+1],for any k <=i} 实现非常简单,代码实现多了这一句,If(LIS[i] > LIS[i+1]) LIS[i+1] =LIS[i]; 在这个子问题空间的定义下,上述的递推关系式是错误的!!!! 首先,我给出一个反例: E.g. array:{5, 6, 2, 3} 最终的LIS[]将是 1 2 2 3, OPT =3, 而该问题的正确结果是2, {5,6}或者{2,3} 分析错误的原因: LIS数组在这种新的定义下,array[k] < array[i+1]并不能保证倒数第二个元素比array[i+1]小,因为此时的子问题LIS[k]并不一定以array[k]为最大元素,例如反例中,LIS[3]=2, 子序列是{5,6}并不以第三个元素也就是3为最大元素,所以出错。
算法3: 引入新的数组: maxV[length+1] 长度为1的递增子序列最大元素的最小值为maxV[1] 长度为2的递增子序列最大元素的最小值为maxV[2] … 长度为LIS[i]的递增子序列最大元素的最小值为maxV[LIS[i]]
首先,证明maxV[]是递增的,因此可以使用二分搜索 用数学归纳法即可证明,下面证明 若前k个元素是递增的,一定有maxV[k+1] >= maxV[k] PROOF:假设不成立,则maxV[k+1] < maxV[k] 根据maxV[k+1]的定义,存在一个长度是k+1的LIS,并且以maxV[k+1]为最大元素。 将上述子序列去掉最后一个元素maxV[k+1], 得到 长度为k,且最大元素 < maxV[k+1] < maxV[k] 这显然与maxV[k]的定义矛盾。。所以假设不成立
《编程之美》上给出了算法的代码。。 算法的思路基本是: 每一步,将array[i]在当前的 maxV[]数组中进行二分搜索,找到位置k maxV[k] < array[i] < maxV[k+1] 注意,array[i]加入后,仅仅影响maxV[k+1] (maxV[k+1] = array[i]) 而对其他的元素不产生影响。 证明: 1. maxV[k]已经它以前的元素不变..较为简单。 2. maxV[k+2]之后的元素不变。。 假设maxV[k+2]需要改变,即加入array[i]后,存在一个长度为k+2的LIS,以array[i]为最大元素。 将上述LIS去掉array[i]得到一个长度为k+1, 且最大元素 < array[i] < maxV[k+1] 的LIS, 这显然与maxV[k+1]的定义矛盾。。得证 复杂度 = O(nlgn) 代码如下:
|
|