本文主要是介绍最长上升子序列 二分优化，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
刚才用O(n^2)的DP算法做了最长上升子序列，后来在网上看到说LIS问题有O(nlogn)的算法，于是拿来小研究了一下。
这个算法其实已经不是DP了，有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n)，每次计算要查找N次还是O(n)，一共就是O(n^2)；现在搜索换成了O(logn)的二分搜索，总的复杂度就变为O(nlogn)了。
这个算法的具体操作如下(by RyanWang):
开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。
这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。
举例：原序列为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。
用该算法完成POJ2533的具体代码如下:
#include <iostream>
#define SIZE 1001using namespace std;int main()
{int i, j, n, top, temp;int stack[SIZE];cin >> n;top = 0;/* 第一个元素可能为0 */stack[0] = -1;for (i = 0; i < n; i++){cin >> temp;/* 比栈顶元素大数就入栈 */if (temp > stack[top]){stack[++top] = temp;}else{int low = 1, high = top;int mid;/* 二分检索栈中比temp大的第一个数 */while(low <= high){mid = (low + high) / 2;if (temp > stack[mid]){low = mid + 1;}else{high = mid - 1;}}/* 用temp替换 */stack[low] = temp;}}/* 最长序列数就是栈的大小 */cout << top << endl;//system("pause");return 0;
}这篇关于最长上升子序列 二分优化的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
