最长递增子序列详解（longestincreasingsubquence）
from /joylnwang/article/details/6766317
2011.09
一个各公司都喜欢拿来做面试笔试题的经典动态规划问题，互联网上也有很多文章对该问题进行讨论，但是我觉得对该问题的最关键的地方，这些讨论似乎都解释的不很清楚，让人心中不快，所以自己想彻底的搞一搞这个问题，希望能够将这个问题的细节之处都能够说清楚。
对于动态规划问题，往往存在递推解决方法，这个问题也不例外。要求长度为i的序列的Ai{a1,a2,……,ai}最长递增子序列，需要先求出序列Ai-1{a1,a2,……,ai-1}中以各元素(a1,a2,……,ai-1)作为最大元素的最长递增序列，然后把所有这些递增序列与ai比较，如果某个长度为m序列的末尾元素aj(j<i)比ai要小，则将元素ai加入这个递增子序列，得到一个新的长度为m+1的新序列，否则其长度不变，将处理后的所有i个序列的长度进行比较，其中最长的序列就是所求的最长递增子序列。举例说明，对于序列A{35, 36, 39, 3, 15, 27, 6, 42}当处
理到第九个元素(27)时，以35， 36， 39， 3， 15， 27， 6为最末元素的最长递增序列分别为
35
35，36
35，36，39
3
3，15
ps改变颜色
3，15，27
3，6
当新加入第10个元素42时，这些序列变为
35，42
35，36，42
35，36，39，42，
3，42
3，15，42
首尾照应3，15，27，42
3，6，42
这其中最长的递增序列为(35，36，39，42)和(3，15，27，42)，所以序列A的最长递增子序列的长度为4，同时在A中长度为4的递增子序列不止一个。
该算法的思想十分简单，如果要得出Ai序列的最长递增子序列，就需要计算出Ai-1的所有元素作为最大元素的最长递增序列，依次递推Ai-2，Ai-3，……，将此过程倒过来，即可得到递推算法，依次推出A1，A2，……，直到推出Ai为止，
代码如下
[cpp] view plain copy
1.unsigned int LISS(const int array[], size_t length, int result[])
2.{
3.unsigned int i, j, k, max;
4.
5.//变长数组参数，C99新特性，用于记录当前各元素作为最大元素的最长递增序列长度
河南经济排名6.unsigned int liss[length];
7.
8.//前驱元素数组，记录当前以该元素作为最大元素的递增序列中该元素的前驱节点，用于打印序列用
9.unsigned int pre[length];
10.
11.for(i = 0; i < length; ++i)
描写月亮的诗句有哪些
12.{
13.liss[i] = 1;
14.pre[i] = i; 工业区位论
15.最后的愿望}
16.
17.for(i = 1, max = 1, k = 0; i < length; ++i)
18.{
19.//找到以array[i]为最末元素的最长递增子序列
20.for(j = 0; j < i; ++j)
21.{
22.//如果要求非递减子序列只需将array[j] < array[i]改成<=，
23.//如果要求递减子序列只需改为>
24.if(array[j] < array[i] && liss[j] + 1> liss[i])
25.{
26.liss[i] = liss[j] + 1;
27.pre[i] = j;
28.
29.//得到当前最长递增子序列的长度，以及该子序列的最末元素的位置
30.if(max < liss[i])
31.{
32.max = liss[i];
33.k = i;
34.}
35.}
36.}
37.}
38.
39.//输出序列
40.i = max - 1;
41.
42.while(pre[k] != k)
43.{
44.result[i--] = array[k];
45.k = pre[k];
46.}
47.
48.result[i] = array[k];
49.
50.return max;
51.}
该函数计算出长度为length的array的最长递增子序列的长度，作为返回值返回，实际序列保存在result数组中，该函数中使用到了C99变长数组参数特性（这个特性比较赞），不支
持C99的同学们可以用malloc来申请函数里面的两个数组变量。函数的时间复杂度为O(nn)，下面我们来介绍可以将时间复杂度降为O(nlogn)改进算法。
在基本算法中，我们发现，当需要计算前i个元素的最长递增子序列时，前i-1个元素作为最大元素的各递增序列，无论是长度，还是最大元素值，都毫无规律可循，所以开始计算前i个元素的时候只能遍历前i-1个元素，来找到满足条件的j值，使得aj < ai，且在所有满足条件的j中，以aj作为最大元素的递增子序列最长。有没有更高效的方法，找到这样的元素aj呢，实际是有的，但是需要用到一个新概念。在之前我举的序列例子中，我们会发现，当计算到第10个元素时，前9个元素所形成最长子序列分别为
35
35，36
35，36，39
3
苹果树下3，15
水煮鸡蛋3，15，27
3，6
这其中长度为3的子序列有两个，长度为2的子序列有3个，长度为1的子序列2个，所以一个序列，长度为n的递增子序列可能不止一个，但是所有长度为n的子序列中，有一个子序列是比较特殊的，那就是最大元素最小的递增子序列（挺拗口的概念），在上述例子中，序列(3)，(3,6)，(3，5，27)就满足这样的性质，他们分别是长度为1，2，3的递增子序列中最大元素最小的（截止至处理第10个元素之前），随着元素的不断加入，满足条件的子序列会不断变化。如果将这些子序列按照长度由短到长排列，将他们的最大元素放在一起，形成新序列B{b1,b2,……bj}，则序列B满足b1 < b2 < …… <bj。这个关系比较容易说明，假设bxy表示序列A中长度为x的递增序列中的第y个元素，显然，如果在序列B中存在元素bmm > bnn，且m < n则说明子序列Bn的最大元素小于Bm的最大元素，因为序列是严格递增的，所以在递增序列Bn中存在元素bnm < bnn，且从bn0到bnm形成了一个新的长度为m的递增序列，因为bmm > bnn，所以bmm > bnm，这就说明在序列B中还存在一个长度为m，最大元素为bnm < bmm的递增子序列，这与序列的定义，bmm是所有长度为m的
递增序列中第m个元素最小的序列不符，所以序列B中的各元素严格递增。发现了如此的一个严格递增的序列，这让我们柳暗花明，可以利用此序列的严格递增性，利用二分查找，找到最大元素刚好小于aj的元素bk，将aj加入这个序列尾部，形成长度为k+1但是最大元素又小于bk+1的新序列，取代之前的bk+1，如果aj比Bn中的所有元素都要大，说明发现了以aj为最大元素，长度为n+1的递增序列，将aj做Bn+1的第n+1个元素。从b1依次递推，就可以在O(nlogn)的时间内找出序列A的最长递增子序列。
