最长递增子序列问题
简述
经典的动态规划问题。
问题描述
给定一个序列，求解其中长度最长的递增子序列。
问题分析
这种可以向下查询答案的很容易想到动态规划的解法。
要求长度为i的序列Ai={a1,a2,a3,ai}的最长递增子序列，需要先求出序列Ai-1{a1,a2,a3,ai-1}中各元素(a1,a1,ai-1)作为最大元素的最长递增子序列，然后将这i-1个递增序列与ai进行比较。如果某个长度为m的序列的末尾元素aj(j<i)比ai小，则将元素ai加入这个递增子序列，得到一个长度为m+1的新序列，否则其长度不变，将处理后的i-1个序列的长度进行比较，最长的就是要求的最长递增子序列。
举个例子 对于序列A{3,1,4,5,9,2,6,5,0}，当处理到第7个元素“6”时，i-1个序列为。 313,43,4,53,4,5,91,2 经过上述处理后，序列变为如下。有两个最长的。可见，以“6”为结尾的最长递增子序列为{3,4,5,6}。 3,61,63,4,63,4,5,63,4,5,91,2,6 同样，处理到第8个元素“5”的时候，原始序列处理后变为如下。 3,51,53,4,53,4,53,4,5,91,2,5 可见，以第8个元素“5”为结尾的最长递增子序列为{3,4,5}。最后一个0，无法在后面添加，因此，这个题目的答案为{3,4,5,9}。序列A的最长递增子序列长度为4.注意：求解到的最长递增子序列可能不止一个。
设f(i)表示序列中以ai为末尾元素的最长递增子序列的长度，则在求以ai为末尾元素的最长递增子序列是，找到所有序号在i前面且小于ai的元素aj，即j<i且aj<ai。
如果这样的元素存在，那么对所有的aj，都有一个以aj为末尾元素的最长递增子序列的长度f(j)。把其中最大的f(j)找出来，f(i)就等于这个最大的f(j)+1。也就是说，以ai为末尾元素的最长递增子序列，等于在使f(j)最大的那个aj为末尾元素的递增子序列最后再加上ai；如果这样的元素不存在，那么自身构成一个长度为1的以ai为末尾元素的递增子序列。
代码
def f(arr):n = len(arr)dp = [0] * nfor i in range(n):dp[i] = 1for j in range(i):if arr[j] < arr[i]:dp[i] = max(dp[i], dp[j]+1)return dpdef generate_lis(arr, dp):n = max(dp)index = dp.index(n)lis = [0] * nn -= 1lis[n] = arr[index]# 从右向左查for i in range(index, -1, -1):if arr[i] < arr[index] and dp[i] == dp[index] - 1:n -= 1lis[n] = arr[i]index = ireturn lisif __name__ == '__main__':arr = [3, 1, 4, 5, 9, 2, 6, 5, 0]print(generate_lis(arr, f(arr)))
这种不确定向下查找的方向的不适合使用递归。
算法改进
上面那种解法的复杂度达到了O(n^2)，其实可以改进为O(nlogn)。在基本算法中，当需要计算前i个元素的最长递增子序列的时候，前i-1个元素作为最大元素的i-1个递增序列，无论是长度，还是最大元素值，都毫无规律，所以在开始计算前i个元素的时候只能遍历前i-1个元素，以找到满足的j值，使得aj<ai且满足条件的j中，以aj作为最大元素的递增子序列最长。
其实。在一个序列中，长度为n的递增子序列可能不只有一个，但是最大元素最小的递增子序列只有一个。上面例子中，当处理第7个元素“6“时，长度为2的子序列有两个，即{3,4}和{1,2}，这个{1,2}就是最大元素最小的递增子序列。（可以轻易证明唯一性）随着序列长度的变化，满足条件的子序列不断变化。
如果将这些子序列安装长度由短到长排序，将每个序列的最大元素放在一起，形成新序列B{b1,b2,bj},则序列B一定是递增的。（此处不证明）
发现了这个严格递增，眼前一亮，可以利用此序列的严格递增进行二分查找，找到最大元素刚好小于aj的元素bk，将aj加入这个序列尾部，形成长度为k+1但是最大元素又小于b(k+1)的新序列，取代之前的b(k+1)。如果aj比B中所有元素都大，说明发现了以aj为最大元素，长度为n+1的递增序列，将aj作为B(n+1)的第n+1个元素。从b1依次递推，可以在O(nlogn)时间内找出A的最长递增子序列。
这种方法大幅度提高了运行效率。优化代码见我的Github
补充说明
-具体代码可以查看我的Github，欢迎Star或者Fork
参考书《你也能看得懂的Python算法书》，书中略微有一点不合理之处，做了修改到这里，其实你已经体会到了动态规划的简约之美，当然，要注意Python是有递归深度限制的，如不是必要，建议使用循环控制。
