最长上升子序列 概念 维基百科-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 <= j < i) 当0<i<n
注解：在序列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<i top 则将a[i]入栈；如果a[i]<= top则二分查找栈中的比a[i]大的第1个数，并用a[i]替换它。 最长序列长度即为栈的大小top。
这是很好理解的，对于x和y，如果x < y且stack[y] < stack[x]，用stack[x]替换stack[y]，此时的最长序列长度没有改变，但序列继续变长的''潜力''增大了。
举例：原序列为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 < n; i++)
if a[i] > s[top] // 将a[i]接在s[top]所代表的子串之后得到一个更长的子序列
top = top + 1
b[top] = a[i]
else
使用二分查找到这样一个j，使得s[j] < a[i] && a[i] <= s[j + 1]
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]<top时呢？ 这时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<j<i>= 0) { s.push(seq[k]); k = pre[k]; } while (!s.empty()) { cout << s.top() << "|"; s.pop(); } cout << endl; delete[] dp; delete[] pre; return max;}//找到一个j满足 array[j] < key <= array[j+1] 区间二分搜索//返回j+1int binary_search(int array[], int key, int low, int high) { while (low <= high) { int mid = (low + high) / 2; if (array[mid] < key && key = array[high] //mid+1不会溢出，想想为什么 return mid + 1; } if (array[mid] < key) { low = mid + 1; } else { high = mid - 1; } }}int lis_greedy(int seq[], int n) { int top = 0; int* stack = new int[n]; for (int i = 0; i < n; ++i) { stack[i] = 0; } stack[top] = seq[0]; for (int i = 0; i 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 <= top; i++) { cout << stack[i] << "|"; } cout << endl; delete[] stack; return top + 1;}int main(int argc, char* argv[]) { //int arr[] = {6,3,7,11,12,10,1,13,8,5,4,15,14,9,2}; int arr[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; int len = sizeof(arr) / sizeof(int); cout << len << endl; cout << lis_dp(arr, len) << endl; cout << lis_greedy(arr, len) << endl; return 0;}/* 第一组测试数据156|7|11|12|13|15|61|2|8|9|13|14|6*/
从测试结果看出，虽然算法一和算法二给出的长度值相等，但是算法二给出本文来源[email protected]搞@^&代*@码网(的序列顺序与原来的不符。
参考：
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
转载请注明原文链接：最长上升子序列 Longest Increasing Subsequence 输出其中一个序
