![序列]( "序列")
最长上升子序列 概念 维基百科-Longest Increasing Subsequence 算法一：动态规划 数据定义： a[] : 输入序列 d[] : 保存最长升序子序列的子问题。 d[i] 表示以a[i]结尾的最长子序列的长度。 d[]初始化为1。因为子序列最短也是1。 n : a 和 d的长度 状态转移 最长上升子序列概念 维基百科->Longest Increasing Subsequence算法一：动态规划数据定义：a[] : 输入序列d[] : 保存最长升序子序列的子问题。 d[i] 表示以a[i]结尾的最长子序列的长度。 d[]初始化为1。因为子序列最短也是1。n : a 和 d的长度状态转移方程：d[0] = 1 当i = 0 d[i] = 1 + max{d[j], a[i] > a[j] && 0 注解：在序列a[0],a[1],a[2],...,a[i-1]中找到最长的一个上升子序列，并且a[i]可以添加在它的末尾，使成为一个更长的上升子序列时间复杂度分析：求解一个d[i]需要一个循环取最大值，时间复杂度为O(n)，所以总的时间复杂度是 O(n^2)。程序使用双重循环构造d数组，最后遍历d数值去最大值。-------------------------------------华丽的分割线------------------------------------------算法二：贪心 + 二分搜索数据定义补充：开一个栈，将a[0]入栈，每次取栈顶元素top和读到的元素a[i](0 top 则将a[i]入栈；如果a[i]这是很好理解的，对于x和y，如果x 举例：原序列为1，5，8，3，6，7开始1，5，8相继入栈，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。伪代码描述： 初始化栈stop = 0;s[top] = a[i];for (i = 1; i if a[i] > s[top] // 将a[i]接在s[top]所代表的子串之后得到一个更长的子序列 top = top + 1b[top] = a[i]else 使用二分查找到这样一个j，使得s[j] s[j + 1] = a[i]return : top + 1算法分析：内层循环由于b序列的严格递增性，可以使用二分查找，时间复杂度为O(log n)，乘以外层循环，最终时间复杂度为O(n log n)。注意：当出现1，5，8，2这种情况时，栈内最后的数是1，2，8不是正确的序列，难道错了？分析一下，我们可以看出，虽然有些时候这样得不到正确的序列，但最后算出来的个数是没错的，为什么呢？想想，当a[i]>top时，总个数直接加1，这肯定没错；但当a[i]这两种情况的分析可以看出，如果只求个数的话，这个算法比较高效；但如果要求打印出序列时，就只能用动态规划了。附上C++代码：#include #include using namespace std;//dp[i] 表示以A[0~i]的最长上升子序列的长度//dp[0] = 1 当i=0//dp[i] = 1 + max{dp[j], 0= 0) {s.push(seq[k]);k = pre[k];}while (!s.empty()) {cout stack[top]) {//如果seq[i]大于栈顶元素，则入栈stack[++top] = seq[i];} else {//从栈底开始，找到第一个>=seq[i]的元素所在位置int replace = binary_search(stack, seq[i], 0, top);stack[replace] = seq[i];}}for (int i = 0; i 登录后复制从测试结果看出，虽然算法一和算法二给出的长度值相等，但是算法二给出的序列顺序与原来的不符。参考：http://www.cnblogs.com/zhtzhl/archive/2012/08/03/2622219.htmlhttp://www.cnblogs.com/zhanglanyun/archive/2011/09/09/2172809.htmlhttp://hi.baidu.com/rffffffff007/item/75353d0c77192810addc70b6 08-30 21:52