最长上升子序列 Longest Increasing Subsequence 输出其中一个序

最长上升子序列 概念 维基百科-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。

伪代码描述： 

初始化栈s

top = 0;

s[top] = a[i];

for (i = 1; i

if a[i] > s[top] // 将a[i]接在s[top]所代表的子串之后得到一个更长的子序列

 top = top + 1

b[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 <iostream>
#include <stack>
using namespace std;
//dp[i] 表示以A[0~i]的最长上升子序列的长度
//dp[0] = 1 当i=0
//dp[i] = 1 + max{dp[j], 0<j int lis_dp seq n new for i="0;" dp pre max="0;" j="0;" if i_max="0;" stack> s;
	int k = i_max;
	while (k >= 0) {
		s.push(seq[k]);
		k = pre[k];
	}
	while (!s.empty()) {
		cout = array[high]
			//mid+1不会溢出，想想为什么
			return mid + 1;
		}
		if (array[mid]  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 从测试结果看出，虽然算法一和算法二给出的长度值相等，但是算法二给出的序列顺序与原来的不符。<br>
<br>

<p>
<strong><br>
</strong></p>
<p>
<span>参考：</span></p>
<p>
<span>http://www.cnblogs.com/zhtzhl/archive/2012/08/03/2622219.html<br>
</span></p>
<p>
<span>http://www.cnblogs.com/zhanglanyun/archive/2011/09/09/2172809.html<br>
</span></p>
<p>
<span>http://hi.baidu.com/rffffffff007/item/75353d0c77192810addc70b6</span><br>
</p>
<p>
<br>
</p>


</j></stack></iostream>