最长递增子序列

文章目录

1. 最长递增子序列

描述

所谓最长递增子序列表示在给定数字序列a1,a2,...,an中，有这么一组子序列ai1,ai2,...,aij，它们满足ai1<ai2<…<aij，它们的下标满足i1<i2<…<ij。我们称这样的序列是自增子序列，那么我们的问题就是求解这个子序列的最大长度是多扫（Longest Increasing Sebsequence），这个问题很像最长公共子序列（LCS）。

思路

首先由于LIS很像LCS，那么这个问题可以用LCS来解决。LCS的输入是两个序列，这里我们只需要将两个相同的序列交给LCS来求，那么LCS的解就是LIS的解了。

第二个方法就是利用动态规划来解。这里需要做个变化，将给定的序列转换成有向无圈图（DAG）。图中的节点就是序列中的数字，如果ai<aj(i<j)，那么数字ai就有条边指向aj。这样我们就构建了一个有向图，根据我们指定的规则，图中肯定没有环。

那么这时候我们的问题就转换成了在这个图中寻找最长的路径。这里我们构造L[i]表示从源点到节点i的图中有最长路径的个数。那么L[i]就是所有指向节点i的最长路径的最大值再加1。它的最优子结构是

最终返回L中的最大值就能得到最长递增子序列。

伪代码

当然在实现的时候我们不需要真的去构建个图，只需要通过两层循环进行判断是否有指向当前节点的点（比当前数字小的数）。

LongestIncreasingSubsequence(An)
Input: numeric sequence An
L[n]; //记录各子序列的长度
for i=1 to n:
	L[i] = 0;
End
for i=1 to n:
	for j=1 to i: //从1到i寻找是否有小于A[i]的A[j]
		if(A[j]<A[i] && L[i]<L[j]+1)
			L[i] = L[j]+1;
		End
	End
End
return max(L,n); //找出L中的最大值

因为需要一维表来储存A[i]的最长递增子序列，所以空间复杂度是O(n)。对每个A[i]都要寻找最长递增子序列，所以这个步骤是O(n^2)，最后寻找最大值的复杂度是O(n)。所以整个复杂度是O(n^2)。

例子

这实际上就是个填表过程，填写一个一维表。

就拿上面的序列来做例子吧，数字序列是5,2,8,6,3,6,9,7。

步骤	L[n]
初始状态	0 0 0 0 0 0 0 0
访问第一个点5	1 0 0 0 0 0 0 0
访问2，5大于2,之间没有线	1 1 0 0 0 0 0 0
访问8，5和2与8均有线，寻找最大值	1 1 2 0 0 0 0 0
访问6，5和2与6均有线，寻找最大值	1 1 2 2 0 0 0 0
访问3，2与3均有线，寻找最大值	1 1 2 2 2 0 0 0
访问6，5、2、3与6均有线，寻找最大值	1 1 2 2 2 3 0 0
访问9，5、2、8、6、3、6与9均有线，寻找最大值	1 1 2 2 2 3 4 4
访问7，5、2、6、3、6、7与7均有线，寻找最大值	1 1 2 2 2 3 4 4

最大值是，所以这个序列的最大递增子序列是4（2,3,6,9和2,3,6,7）。