当前位置：文档之家› 求数组中最长递增子序列

求数组中最长递增子序列

写一个时间复杂度尽可能低的程序，求一个一维数组（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]]

解法一

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

同样的，仍以序列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的子序列。

根据上面的分析，就可以得到代码清单

C++代码：

int Max(int *a, int n)

{

int max = a[0];

for(int i = 1; i < n; i++)

if(max < a[i])

max = a[i];

return max;

}

int LIS(vector &array)

{

int *a = new int[array.size()];

for(int i = 0; i < array.size(); i++)

{

a[i] = 1; //初始化默认的长度

for(int j = 0; j < i; j++) //前面最长的序列

{

if(array [i] > array [j] && a[j] + 1 > a[i])

{

a[i] = a[j] + 1;

}

return Max(a, array.size());

}

这种方法的时间复杂度为O(N2 + N) = O(N2)

解法二

在前面的分析中，当考察第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]];

本循环不变式P是：

P：k是序列a[0:i]的最长递增子序列的长度，0≤i＜n。

容易看出，在由i-1到i的循环中，a[i]的值起关键作用。如果a[i]能扩展序列a[0;i-1]的最长递增子序列的长度，则k=k+1，否则k不变。设a[0;i-1]中长度为k的最长递增子序列的结尾元素是a[j](0≤j≤i-1)，则当a[i]≥a[j]时可以扩展，否则不能扩展。如果序列a[0;i-1]中有多个长度为k的最长递增子序列，那么需要存储哪些信息？容易看出，只要存储序列a[0;i-1]中所有长度为k的递增子序列中结尾元素的最小值b[k]。因此，需要将循环不变式P增强为：

P：0≤i＜n;k是序列a[0;i]的最长递增子序列的长度；

b[k]是序列a[0;i]中所有长度为k的递增子序列中最小结尾元素值。

相应地，归纳假设也增强为：已知计算序列a[0;i-1](i＜n)的最长递增子序列的长度k以及序列a[0;i]中所有长度为k的递增子序列中的最小结尾元素值b[k]的正确算法。

增强归纳假设后，在由i-1到i的循环中，当a[i]≥b[k]时，k=k+1，b[k]=a[i],否则k值不变。注意到当a[i]≥b[k]时，k值增加，b[k]的值为a[i]。那么，当a[i]＜b[k]时，b[l;k]的值应该如何改变？如果a[i]

/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */

template vector find_lis(vector &a)

{

vector b, p(a.size());//b是存储递增序列长度为k的最后元素下标

//比如b[1]是存储递增子序列最大元素的最小值的下标

//b是存储最长子序列的下标

int u, v;

if(a.size() < 1)

return b;

b.push_back(0);

for(int i = 1; i < (int)a.size(); i++)

{

if(a[b.back()] < a[i])

p[i] = b.back();

b.push_back(i);

continue;

}

for(u = 0, v = b.size()-1; u < v;) //二分搜索

{

int c = (u + v) / 2;

if(a[b[c]] < a[i])

u=c+1;

else

v=c;

}

if(a[i] < a[b[u]]) {

if(u > 0)

p[i] = b[u-1];

b[u] = i;

}

for(u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;

return b;

最长公共子序列问题(最)

算法作业： LCS 问题作业要求：设计一个算法求出两个序列的所有LCS ，分析最坏情况，用“会计方法”证明利用b[i][j]求出所有LCS 的算法在最坏情况下时间复杂度为)(m m n C O + 1、算法思路：根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={x 1, x 2, … , x n }, Y={y 1, y 2, … , y m }, 首先引入二维数组C[i][j]记录X i 和Y j 的LCS 的长度，定义C[i][j]如下： { j i j y i 且x ,i,j ]][j C[i j y i x j i j i C j i C j i C 00001110,]},1][[],][1[max{]][[===>+--≠>--=或，且为了构造出LCS ，还需要使用一个二维数组b[m][n]，b[i][j]记录C[i][j]是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的LCS ，定义数组b 如下：设1-对角线方向;2-向上;3-向左;4-向上或向左若X[i]=Y[j],b[i][j] = 1, 若C[i-1][j][i][j-1], 则b[i][j] = 3, 若C[i-1][j]=[i][j-1], 则b[i][j] = 4, 根据以上辅助数组C 和b 的定义，算法首先需要求出这两个数组， C[m][n]中记录的最长公共子序列的长度，b 中记录了查找子序列元素的搜索方向。利用C 和b 的信息，Find_All_LCS 可以采用回溯法求出所有的LCS 。基本思路如下：使用一个辅助数组记录每次调用Find_All_LCS 得到的LCS 中的元素，每次递归调用一次Find_All_LCS ，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组C 中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个LCS ，按序输出；若不等于，此时根据数组b 中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用Find_All_LCS ，保证沿着这两个方向上LCS 元素不被漏掉，都可以搜索到；若b[i][j]=1，即沿对角线方向搜索前进时，此时元素X[i]为LCS 中的元素，存放至辅助数组中去，同时将当前已经求得的LCS 长度增1，当递归调用Find_All_LCS 从b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为LCS 中的元素。当所有的可能路径都已经搜索完，算法结束。对于某些情况会输出重复的LCS ，这是因为算法在沿不同路径搜索时可能会出现相同的LCS 序列。 2、时间复杂度分析由上述对Find_All_LCS 算法的分析可知，求出所有的LCS 实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此，除求解辅助数组C 和b 所用的O(mn+m+n)的执行时间外，Find_All_LCS 的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的情况下，即m=n 并且b 中所有的值都指示沿着对角线方向搜索，时间复杂度为O(n). 相反，当X 和Y 序列不存在公共子序列时为算法的最坏情况，此时C 中所有值都等于0，数组b 中所有的值都指示要分别沿两个不同的方向（向左或向上）搜索，这种情况下每处理一次X[i],Y[j]时总是要沿两个方向分别调用Find_All_LCS ，遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束，最坏情况下的搜索矩阵如下图所示：