「最长递增子序列java」最长递增子序列nlogn
今天给各位分享最长递增子序列java的知识，其中也会对最长递增子序列nlogn进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、如何求一个（正数）无序数组中最长有序子数组的长度？
- 2、给定一个顺序存储的线性表,请设计一个算法,查找该线性表中最长递增子序列
- 3、用java求，给定一个字符串,求其中最大连续递增的数字子串(如"acb125vf13679dD4562789ABCDEF"中的"13679")
- 4、JAVA动态规划，最长递增子序列的代码太难理解，求大神帮我讲解一下！
如何求一个（正数）无序数组中最长有序子数组的长度？
据题目的要求，求一维数组中的最长递增子序列，也就是找一个标号的序列b[0],b[1],…,b[m](0 = b[0] b[1] … b[m] N)，使得array[b[0]]array[b[1]]…array[b[m]]。
根据无后效性的定义我们知道，将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态来说，它以前各阶段的状态无法直接影响它未来的决策，而只能间接地通过当前的这个状态来影响。换句话说，每个状态都是历史的一个完整总结。
同样的，仍以序列1，-1，2，-3，4，-5，6，-7为例，我们在找到4之后，并不关心4之前的两个值具体是怎样，因为它对找到6没有直接影响。因此，这个问题满足无后效性，可以通过使用动态规划来解决。
可以通过数字的规律来分析目标串：1，-1，2，-3，4，-5，6，-7。
使用i来表示当前遍历的位置
当i=1时，显然，最长的递增序列为（1），序列长度为1.
当i=2是，由于-11。因此，必须丢弃第一个值后重新建立串。当前的递增序列为（-1），长度为1。
当i=3时，由于21,2-1。因此，最长的递增序列为（1,2）,(-1,2),长度为2。在这里，2前面是1还是-1对求出后面的递增序列没有直接影响。（但是在其它情况下可能有影响）
依此类推之后，我们得出如下的结论。
假设在目标数组array[]的前i个元素中，最长递增子序列的长度为LIS[i]。那么，
LIS[i+1]=max{1,LIS[k]+1}, array[i+1]array[k], for any k = i
即如果array[i+1]大于array[k],那么第i+1个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。
根据上面的分析，就可以得到代码清单：
C++代码：
代码如下:
int Max(int *a, int n)
{
int max = a[0];
for(int i = 1; i n; i++)
if(max a[i])
max = a[i];
return max;
}
int LIS(vectorint array)
{
int *a = new int[array.size()];
for(int i = 0; i array.size(); i++)
{
a[i] = 1;//初始化默认的长度
for(int j = 0; j i; j++) //前面最长的序列
{
if(array [i] array [j] a[j] + 1 a[i]) //当前数字比第j个大，且标记数组需要更新
{
a[i] = a[j] + 1;
}
}
}
return Max(a, array.size());
}
这种方法的时间复杂度为O(N2 + N) = O(N2)
给定一个顺序存储的线性表,请设计一个算法,查找该线性表中最长递增子序列
解法1：
很明显用动态规划的算法，选取下面的阶段（这种选法极为常见），可使阶段间的关系具有无后效性。
阶段：在所有以元素k结尾的子数组中，选出其中的最长递增子序列，k=1,2...n。
状态：以元素k结尾的最长递增子序列中只有一个最长的递增子序列。
决策：决定元素k结尾的最长递增子序列有k-1种获取的途径，前面以任何一个元素结尾的最长递增子序列都可能成为其的一部分。
这样的时间复杂度为O(n^2)，空间复杂度为O(n)
#include iostream
#include algorithm
using namespace std;
#define MAXN 1003
int A[MAXN];
int dp[MAXN];
// 动态规划思想O(n^2)
int main()
{
int n, i, j, k;
cin n;
for (i=1; i=n; i++)
cin A[i];
dp[1] = 1;
// 有n个阶段
for (i=2; i=n; i++)
{
dp[i] = 1; // 每个阶段只有1个状态
// 每个状态有i种决策,以得出以元素i结尾的最长递归子序列的长度
for (j=i-1; j=0; j--)
{
if (A[i]A[j])
dp[i] = max(dp[i], dp[j]+1);
}
}
int maximum = dp[1];
for (i=2; i=n; i++)
maximum = max(maximum, dp[i]);
cout maximum;
}
解法2：
动态规划的时间复杂度一般与空间复杂度相同，因为决定下一个阶段的所有条件我们已存储到dp中，在处理过程中我们可以对已得到的这些条件进行处理来降低时间复杂度。而这里时间复杂度竟比空间复杂度高了O(n)，说明还有可以继续优化的空间。
我们可以统计前面所有阶段的最长递增子序列的长度，将长度相同的最长递增子序列分到同一组中，并只记录它们最大元素的最小值MaxV[长度值]，如果阶段k的元素大于长度为i最长递增子序列的这个最小值MaxV[i]，那么阶段k的最长递增子序列的长度至少为i+1。
而我们发现统计出的MaxV数组具有很好的递增关系（动态规划都是用来解决最优化问题，我们总能通过优化关系对之前统计出的结果进行排序），即如果ij，那么有MaxV[i]MaxV[j]，最后用二分查找法来阶段k的元素在MaxV数组中的位置即可。
证明：反证法，假设当ij=k，有MaxV[i]=MaxV[j]，那么存在一个长度为i的递增序列a1a2...ai，且ai是计算到阶段k时所有长度为i的递增序列中最大元素的最小值，以及长度为j的序列b1b2...bj且ai=bj，由于ij长度j的序列b1b2...bj包含一个子序列b1b2...bi，且bibj=ai，即长度为i的递增子序列最大元素的最小值不是ai，矛盾。
#include iostream
#include algorithm
using namespace std;
#define MAXN 1003
int A[MAXN];
int MaxV[MAXN];
// 动态规划算法O(nlogn)
int main()
{
int n, i, j, k;
cin n;
for (i=1; i=n; i++)
cin A[i];
MaxV[1] = A[1];
int nmaxv = 1; // 目前找到的最长递增子序列的长度
// 有n个阶段，每个阶段有1个状态
for (i=2; i=n; i++)
{
// 每个状态有nmaxv种决策，以得出以元素i结尾的最长递归子序列的长度
int u = 1, v = nmaxv;
while (u=v)
{
int mid = (u+v)1;
if (MaxV[mid] A[i])
u = mid+1;
else
v = mid-1;
}
// 每个元素都会对数组MaxV中的某个元素产生影响
// 使用二分搜索确定其在第v+1个位置
nmaxv = max(nmaxv, v+1);
MaxV[v+1] = A[i];
}
cout nmaxv;
}
用java求，给定一个字符串,求其中最大连续递增的数字子串(如"acb125vf13679dD4562789ABCDEF"中的"13679")
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Number {
public static void main(String[] args) {
StringBuilder stb=new StringBuilder("0,0");//容器!
String str="acb125vf13679dD4562789ABCDEF";//原串!
Matcher matcher=Pattern.compile("\\d+").matcher(str);//匹配!
for(int count=0;matcher.find();) {//挑选!
str=matcher.group();
for(int i=0;istr.length()-1;i++) {//查看指定规则次数:
if(str.charAt(i)str.charAt(i+1))
count++;
else
break;
}//如果,重新获取的比以前存入的次数更多,就放弃原来存入新的!
if(Integer.parseInt(stb.substring(0,stb.lastIndexOf(",")))count) {
stb.delete(0, stb.length());
stb.append(count+","+str);
}//每次查看,为了查看,这个可有可无!
System.out.println(str+"\t递增次数:\t"+count);
count=0;//计数器归零!
}//最后容器里面存入的就是最大的,取出来即可!
System.out.println("最多的是:"+stb.substring(stb.lastIndexOf(",")+1)+"\t次数是:\t"+stb.substring(0,stb.lastIndexOf(",")));
}
}
JAVA动态规划，最长递增子序列的代码太难理解，求大神帮我讲解一下！
第一层的 if 逻辑表示 如果新的一个数A[i]对于 B[]中的数来说是递增的，则len加1，这是记录递增数列长度的主要逻辑。else中的逻辑保证B[]中的数列是最新的递增数列。
举个例子，如果A数组为[1,2,3,4,5, 3.1, 3.2, 3.3, 3.4]
当i=4时 len=4 B=[x,1,2,3,4,x] 循环结束后 len=5 B=[x,1,2,3,4,5] 第一层判断走if
当i=5时 len=5 B=[x,1,2,3,4,5] 循环结束后 len=5 B=[x,1,2,3,3.1,5] 第一层判断走else
当i=6时 len=5 B=[x,1,2,3,3.1,5] 循环结束后 len=5 B=[x,1,2,3,3.1,3.2] 第一层判断走else
当i=7时 len=5 B=[x,1,2,3,3.1,3.2] 循环结束后 len=6 B=[x,1,2,3,3.1,3.2,3.3] 第一层判断走else
...
其中第一层的else中做的工作就是把B从[x,1,2,3,4,5] 一步步变成 [x,1,2,3,3.1,3.2],最终B[]的最后一个元素变成3.2, 在下一次A[i]=3.3的时候，就又会走第一次if的逻辑（len加1）了。
最长递增子序列java的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于最长递增子序列nlogn、最长递增子序列java的信息别忘了在本站进行查找喔。
发布于：2022-12-26，除非注明，否则均为原创文章，转载请注明出处。