求数组中最长递增子序列.doc

求数组中最长递增子序列写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。分析与解法根据题目的要求，求一维数组中的最长递增子序列，也就是找一个标号的序列b0,b1,bm(0 = b0 b1 bm N)，使得arrayb0arrayb1arraybm。 解法一根据无后效性的定义我们知道，将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态来说，它以前各阶段的状态无法直接影响它未来的决策，而只能间接地通过当前的这个状态来影响。换句话说，每个状态都是历史的一个完整总结。同样的，仍以序列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是，由于-11,2-1。因此，最长的递增序列为（1,2）,(-1,2),长度为2。在这里，2前面是1还是-1对求出后面的递增序列没有直接影响。（但是在其它情况下可能有影响）依此类推之后，我们得出如下的结论。假设在目标数组array的前i个元素中，最长递增子序列的长度为LISi。那么，LISi+1=max1,LISk+1,arrayi+1arrayk,for any k = i即如果arrayi+1大于arrayk,那么第i+1个元素可以接在LISk长的子序列后面构成一个更长的子序列。于此同时arrayi+1本身至少可以构成一个长度为1的子序列。根据上面的分析，就可以得到代码清单C+代码：int Max(int *a, int n) int max = a0; for(int i = 1; i n; i+) if(max ai)max = ai; return max;int LIS(vector &array)int *a = new intarray.size();for(int i = 0; i array.size(); i+)ai = 1; /初始化默认的长度for(int j = 0; j array j & aj + 1 ai)ai = aj + 1;return Max(a, array.size();这种方法的时间复杂度为O(N2 + N) = O(N2) 解法二在前面的分析中，当考察第i+1个元素的时候，我们是不考虑前面i个元素的分布情况的。现在我们从另一个角度分析，即当考察第i+1个元素的时候考虑前面i个元素的情况。对于前面i个元素的任何一个递增子序列，如果这个子序列的最大的元素比arrayi+1小，那么就可以将arrayi+1加在这个子序列后面，构成一个新的递增子序列。比如当i=4的时候，目标序列为1，-1，2，-3，4，-5，6，-7最长递增序列为(1,2),(-1,2)。那么，只要42,就可以把4直接增加到前面的子序列中形成一个新的递增子序列。因此，我们希望找到前i个元素中的一个递增子序列，使得这个递增子序列的最大的元素比arrayi+1小，且长度尽量地长。这样将arrayi+1加在该递增子序列后，便可以找到以arrayi+1为最大元素的最长递增子序列。仍然假设在数组的前i个元素中，以arrayi为最大元素的最长递增子序列的长度为LISi。同时，假设：长度为1的递增子序列最大元素的最小值为MaxV1;长度为2的递增子序列最大元素的最小值为MaxV2;长度为LISi的递增子序列最大元素的最小值为MaxVLISi; 本循环不变式P是：P：k是序列a0:i的最长递增子序列的长度，0in。容易看出，在由i-1到i的循环中，ai的值起关键作用。如果ai能扩展序列a0;i-1的最长递增子序列的长度，则k=k+1，否则k不变。设a0;i-1中长度为k的最长递增子序列的结尾元素是aj(0ji-1)，则当aiaj时可以扩展，否则不能扩展。如果序列a0;i-1中有多个长度为k的最长递增子序列，那么需要存储哪些信息？容易看出，只要存储序列a0;i-1中所有长度为k的递增子序列中结尾元素的最小值bk。因此，需要将循环不变式P增强为：P：0in;k是序列a0;i的最长递增子序列的长度；bk是序列a0;i中所有长度为k的递增子序列中最小结尾元素值。相应地，归纳假设也增强为：已知计算序列a0;i-1(in)的最长递增子序列的长度k以及序列a0;i中所有长度为k的递增子序列中的最小结尾元素值bk的正确算法。增强归纳假设后，在由i-1到i的循环中，当aibk时，k=k+1，bk=ai,否则k值不变。注意到当aibk时，k值增加，bk的值为ai。那么，当aibk时，bl;k的值应该如何改变？如果aibl,则显然应该将bl的只改变为ai,当blaibk时，注意到数组b是有序的，可以用二分搜索算法找到下标j，使得bj-1aibj。此时，b1;j-1和bj+1;k的值不变，bj的值改变为ai。/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */template vector find_lis(vector &a)vector b, p(a.size();/b是存储递增序列长度为k的最后元素下标 /比如b1是存储递增子序列最大元素的最小值的下标/b是存储最长子序列的下标 int u, v; if (a.size() 1)return b; b.push_back(0); for (int i = 1; i (int)a.size(); i+) if (ab.back() ai) pi = b.back(); b.push_back(i); continue; for (u = 0, v = b.size()-1; u v;) /二分搜索 int c =