常州网站制作费用,太原建站,wordpress入侵工具,网站被降权的表现单调子序列包含有单调递增子序列和递减子序列#xff0c;不失一般性#xff0c;这里只讨论单调递增子序列。首先#xff0c;从定义上明确我们的问题。给定序列a1, a2, …, an#xff0c;如果存在满足下列条件的子序列 ai1ai2…aim, (其中i1i2…im)…单调子序列包含有单调递增子序列和递减子序列不失一般性这里只讨论单调递增子序列。首先从定义上明确我们的问题。给定序列a1, a2, …, an如果存在满足下列条件的子序列 ai1ai2…aim, (其中i1i2…im) 即称为一个原序列的长度为m的单调递增子序列那么现在的问题是我们要找出一个序列的最长的单调递增子序列。 直观上来说一个序列Sn它有2n个子序列枚举所有的子序列找出其中单调递增的序列然后返回其中最长的这样我们的问题就解决了。当然这个直观的算法在时间上为O(2n*n)它的复杂度增长太快了所以我们还应该做得更好一些。 于是我们换个角度思考。假设我们对Sn排序递增得到Sn’。那么Sn和Sn’的最长公共子序列Cm就是我们要求的最长单调递增子序列如果你不清楚最长公共子序列的定义just google it。为什么假设Cm’是Sn的最长单调子列且Cm’!Cm Cm’的长度大于Cm。由于Cm’是递增的并且Cm’的每一个元素都来自Sn所以Cm’一定是Sn’的子列而Cm’又是Sn的子列所以Cm’是Sn和Sn’的公共子列故Cm’的长度一定小于Cm这与假设矛盾所以Cm是最长单调子列。理论上我们的算法是正确的复杂度方面运用动态规划(dynamic programming)来求解LCS最长公共子列Longest-Common-Subsequence时间上是O(n2)空间上也是O(n2)。于是对Sn排序需要nlogn的时间而LCS需要n2最后我们的算法时间上是O(n2)。 可以看到通过上面的改进我们的算法效率得到了很大的提升从指数增长到多项式增长。不过程序设计的乐趣就是它会不断地给我们一些惊喜所以就此打住不是我们该做的于是更好的算法应该是存在的。 对于序列Sn考虑其长度为i的单调子列(1im)这样的子列可能有多个。我们选取这些子列的结尾元素子列的最后一个元素的最小值。用Li表示。易知 L1L2…Lm 如果LiLj(ij)那么去掉以Lj结尾的递增子序列的最后j-i个元素得到一个长度为i的子序列该序列的结尾元素akLjLi这与Li标识了长度为i的递增子序列的最小结尾元素相矛盾于是证明了上述结论。现在我们来寻找Sn对应的L序列如果我们找到的最大的Li是Lm那么m就是最大单调子列的长度。下面的方法可以用来维护L。 从左至右扫描Sn对于每一个ai它可能 (1) aiL1那么L1ai (2) aiLm那么Lm1aimm1 (其中m是当前见到的最大的L下标) (3) LsaiLs1那么Ls1ai 扫描完成后我们也就得到了最长递增子序列的长度。从上述方法可知对于每一个元素我们需要对L进行查找操作由于L有序所以这个操作为logn于是总的复杂度为O(nlogn)。优于开始O(n2)的算法。这里给出我的一个实现算法并没有返回具体的序列只是返回长度 1 template typename T 2 int LMS (const T * data, int size) 3 ...{ 4 if (size 0) 5 return 0; 6 7 T * S new T[size]; 8 int S_Count 1; 9 S[0] data[0];10 11 for (int i 1; i size; i)12 ...{13 const T e data[i];14 int low 0, high S_Count - 1;15 16 while (low high)17 ...{18 int mid (low high) / 2;19 20 if (S[mid] e)21 break;22 else if (S[mid] e)23 ...{24 high mid - 1;25 }26 else27 ...{28 low mid 1;29 }30 }31 32 //well, in this point33 //high is -1, indicating e is the smallest element.34 //otherwise, high indicates index of the largest element that is smaller than e35 if (high S_Count - 1)36 S[S_Count] e;37 else38 S[high 1] e;39 }40 41 return S_Count;42 } 转载于:https://www.cnblogs.com/ITXIAZAI/p/4111294.html
