正文

编程之美2.16最长递增子序列

brucemengbm  brucemengbm  2022-08-28  182

关键词：

这道题目要求返回一个数字。这个数字代表一个数组中最长的递增子序列，当然。不要求这个序列是连续的。比方，有这样一个数组：{1, 3，5。7, 2, 9}，那么这个数组的最长递增子序列就是5。即1, 3, 5, 7，9

解决这道题目的思想就是：后面的数字仅仅要是大于前面递增子序列的最大值，那么，它就一定大于前面全部的序列，既然须要知道前面保存的序列，那么，我们这里就须要一个辅助数组。数组中存储的就是“最小的连续递增子数组”。我们操作这个数组时。须要遵循两个规律：

假设这个辅助数组为空，那么直接把原数组的数字放入当中

1.假设原数组中的数字大于辅助数组的最大数字（即最后一个数字）。那么。直接把原数组中的数放入当中就能够了，并把递增序列值加 1

2.假设原数组中的数字小于等于辅助数组的最大数字，那么。因为我们须要的是最小的连续递增子数组，所以，须要替换辅助数组中的值。这里，我们能够利用二分查找的办法（因为辅助数组是有序的），找到恰好比当前数字大的那个数字。替换掉即可了

最后。返回辅助数组的长度就能够了：

函数声明：

/*2.16 最长递增子序列*/
int DutBinFindForLRS(int*, int, int);
int DutLRS(int*, int);

源码：

/*二分查找*/
int DutBinFindForLRS(int* A, int size, int v)
{
	if (!A || size <= 0)
		return -1;

	int low = 0;
	int high = size - 1;

	while (low <= high)
	{
		int mid = low + (high - low) / 2;

		if (v >= A[mid])
			low = mid + 1;
		else
			high = mid - 1;
	}

	return low;
}

int DutLRS(int* A, int size)
{
	if (!A || size <= 0)
		return 0;

	int len = 1;
	int* tmp = new int[size];
	tmp[0] = A[0];

	for (int i = 1; i < size; ++i)
	{
		if (A[i] > tmp[len - 1])
			tmp[len++] = A[i];
		else
		{
			int pos = DutBinFindForLRS(tmp, len, A[i]);

			tmp[pos] = A[i];
		}
	}

	delete[] tmp;
	tmp = NULL;

	return len;
}

动态规划--最长递增子序列

经典的最长子序列问题，最近编程训练遇到此题苦无思路，在网上找到比较规范的解答，细思两天后还是觉得有点问题，现在整理总结如下：参照 https://www.cnblogs.com/hapjin/p/5597658.html1.问题描述：给定一个序列，求解它的... 查看详情

网络流24题最长递增子序列问题

...定序列中最多可取出多少个长度为s的递增子序列。«编程任务：设计有效算法完成（1）（2）（3）提出的计算任务。输入输出格式输入格式：第1行有1个正整数n，表示给定序列的长度查看详情

网络流24题最长递增子序列问题

...从给定序列中最多可取出多少个长度为s的递增子序列。编程任务：设计有效算法完成（1）（2）（3）提出的计算任务。输入输出格式输入格式：第1行有1个正整数n，表示给定序列的长度。接下来查看详情

使用分而治之找到最长的递增子序列

...法正确回答，后来当我检查时，我发现它是一个基于动态编程的算法。我不精通动态编程，但假设我要设计这个算法，那么我应该如何处理它？假设，我从MergeSort等其查看详情

最长递增子序列&&最大子序列最长递增子序列最长公共子串最长公共子序列字符串编辑距离

http://www.cppblog.com/mysileng/archive/2012/11/30/195841.html最长递增子序列问题：在一列数中寻找一些数，这些数满足：任意两个数a[i]和a[j]，若i<j，必有a[i]<a[j]，这样最长的子序列称为最长递增子序列。设dp[i]表示以i为结尾... 查看详情

最长递增子序列

给定数组arr，返回arr最长递增子序列。举例：arr=[2,1,5,3,6,4,8,9,7],返回的最长递增子序列是[1,3,4,8,9]。方法：建立dp[i]数组,每一位表示以这一位结尾的最长递增子序列，然后根据最大值求出子序列。时间复杂度为O(n^2).代码... 查看详情

最长递增子序列

】最长递增子序列【英文标题】：Longestincreasingsubsequence【发布时间】：2011-04-2821:46:03【问题描述】：给定一个输入序列，找到最长（不一定是连续的）递增子序列的最佳方法是什么[0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]#input[1,9,13,15]#anexa... 查看详情

最长递增子序列的潜在 O(n) 解

...【问题描述】：我试图回答这个问题，只使用递归（动态编程）http://en.wikipedia.org/wiki/Longest_increasing_subsequence从这篇文章中，我意识到最有效的现有解决方案是O(nlgn)。我的解决查看详情

51nod1134最长递增子序列(代码片段)

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）例如：516824510，最长递增子序列是124510。收起输入第1行：1个数N，N为序列的长度(2<=N<=50000)第2-N+1行：每行1个数，... 查看详情

51nod1134最长递增子序列

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）例如：516824510，最长递增子序列是124510。 Input第1行：1个数N，N为序列的长度(2 <= N <= 50000)第2 - N&nb... 查看详情

51nod1134最长递增子序列

4.5最长递增子序列

【题目】：　　　　给定数组arr，返回arr的最长递增子序列　　举例：　　　　　　arr=[2,1,5,3,6,4,8,9,7]，返回的最长递增子序列为[1,3,4,8,9]【要求】：　　如果arr长度为N，请实现时间复杂度为O(NlogN)的方法查看详情

nyoj17单调递增最长子序列

单调递增最长子序列时间限制：3000 ms | 内存限制：65535 KB难度：4描写叙述求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4输入第一行一个整数0<n<20,表示有n个字符串要处理随... 查看详情

单调递增最长子序列

...bsp;内存限制：65535 KB难度：4 描述求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4 输入第一行一个整数0<n<20,表示有n个字符串要处理随后的n行，每行有一个字符串，该字符串的长... 查看详情

[网络流24题]最长递增子序列问题

题目大意：给定长度为n的序列a，求：1.最长递增子序列长度；2.最多选出几个不相交的最长递增子序列；3.最多选出几种在除了第1个和第n个以外的地方不相交的最长递增子序列。（n<=1000）思路：先倒着DP，求出f[i]表示以a[i]开... 查看详情

nyoj题目17单调递增最长子序列

单调递增最长子序列时间限制：3000 ms | 内存限制：65535 KB难度：4 描述求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4 输入第一行一个整数0<n<20,表示有n个字符串要处... 查看详情

nyoj单调递增最长子序列(代码片段)

单调递增最长子序列（动态规划）(代码片段)

单调递增最长子序列题目描述:求一个字符串的最长递增子序列的长度如：dabdbf最长递增子序列就是abdf，长度为4输入描述:第一行一个整数0<n<20,表示有n个字符串要处理随后的n行，每行有一个字符串，该字符串的长度不会超... 查看详情