最长上升子序列 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#include using namespace std; //dp[i] 表示以A[0~i]的最长上升子序列的长度 //dp[0] = 1 当i=0 //dp[i] = 1 + max{dp[j], 0 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 从测试结果看出，虽然算法一和算法二给出的长度值相等，但是算法二给出的序列顺序与原来的不符。
参考：
http://www.cnblogs.com/zhtzhl/archive/2012/08/03/2622219.html
http://www.cnblogs.com/zhanglanyun/archive/2011/09/09/2172809.html
http://hi.baidu.com/rffffffff007/item/75353d0c77192810addc70b6