最长上升子序列LongestIncreasingSubsequence输出其中一个序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了最长上升子序列LongestIncreasingSubsequence输出其中一个序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4136字，纯文字阅读大概需要6分钟。

内容图文

最长上升子序列 概念 维基百科-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<n)做比较，如果a[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并且A[j] s;
	int k = i_max;
	while (k >= 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+1
int binary_search(int array[], int key, int low, int high) {
	while (low <= high) {
		int mid = (low + high) / 2;
		if (array[mid] < key && key <= array[mid+1]) { 
			//由于array严格单调递增，又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 < n; ++i) {
		if (seq[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;
}
/* 第一组测试数据
15
6|7|11|12|13|15|
6
1|2|8|9|13|14|
6
*/

参考：

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

内容总结

以上是互联网集市为您收集整理的最长上升子序列LongestIncreasingSubsequence输出其中一个序全部内容，希望文章能够帮你解决最长上升子序列LongestIncreasingSubsequence输出其中一个序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端