「java最长递子序列」java最大连续子序列
今天给各位分享java最长递子序列的知识，其中也会对java最大连续子序列进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
- 1、java怎么写求最长的公共子序列
- 2、java 求最大子序列和问题递归求解报越界异常
- 3、如何求一个（正数）无序数组中最长有序子数组的长度？
- 4、求一个整数序列的最长递增子序列。
- 5、JAVA动态规划，最长递增子序列的代码太难理解，求大神帮我讲解一下！
java怎么写求最长的公共子序列
/*目标：输出两个字符串的所有公共最长子序列date:09-11-26BY:zggxjxcgx算法：判断较短串是否为较长串的子序列，如果是则得到结果；否则，对较短串进行逐个字符删除操作（将字符替换为'#'表示删除）。删除操作用递归函数进行实现。每层递归删除一个字符，若删除一个字符后未得到匹配子序列，则还原该字符所在位置。第n层递归未找到匹配子序列，则将递归层数加1，重复删除直到剩下空串。*/#include#includeintdep=0;/*较短串的长度*/intdepflag=0;/*下一步要探测的深度*/intlastflag=0;/*是否找到匹配子序列，1为找到*/intcount=0;/*目标结果的个数*/intmystrcmp(char*s1,char*s2)/*判断s2是否为s1的子串*/{while(*s1*s2)if(*s2=='#')s2++;elseif(*s2==*s1){s1++;s2++;}elses1++;while(*s2=='#')s2++;if(*s2=='\0')return1;return0;}voidpristr(char*str)/*打印最长子序列*/{if(0==count++)printf("\n公共最长子序列：\n");printf("%2d:",count);while(*str){if(*str!='#')printf("%c",*str);str++;}printf("\n");}/*递归函数求最长子序列。start控制下一个要检测的字符,deptemp控制递归的深度,first为's'表示第一层递归*/intfun(char*str1,char*str2,char*start,intdeptemp,charfirst){inti=0,j=0;char*s,cback;do{s=start;if('s'==first)deptemp=depflag;/*在第一层设置递归深度*/while(*s){if(*s=='#'){s++;continue;}cback=*s;*s='#';/*删除当前字符*/if(mystrcmp(str1,str2)){pristr(str2);lastflag=1;}/*找到匹配，将lastflag设为1，在完成深度为deptemp+1的探测（找到所有匹配）后退出递归*/elseif(deptemp0)fun(str1,str2,s+1,deptemp-1,'n');/*深度探测，s+1表示从下一个位置开始删除*/*s=cback;s++;/*还原该位置的字符，以便下次进行探测*/}if('s'==first)++depflag;/*删除depflag+1个字符还未找到，则递归深度加1*/}while(depflagstrlen(st2))s1=st1,s2=st2;/*将s1设为较长的串*/elses1=st2,s2=st1;printf("\nstr1:%s\nstr2:%s\n",s1,s2);dep=strlen(s2);/*得到较短串的长度*/if(mystrcmp(s1,s2))pristr(s2);elseif(0==fun(s1,s2,s2,0,'s'))printf("\n没有公共元素！\n");//printf("%d\n",mystrcmp("afdebjewcwedw","abcdw#"));}
java 求最大子序列和问题递归求解报越界异常
第二个测试用例中，空数组的长度为0
return
maxSubSumRec(array,0,array.length-1);
这就导致这一步调用传入的实参为
return
maxSubSumRec(array,0,-1);
所以，导致数组越界。
如何求一个（正数）无序数组中最长有序子数组的长度？
据题目的要求，求一维数组中的最长递增子序列，也就是找一个标号的序列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)
求一个整数序列的最长递增子序列。
经典的LIS问题.
但从算法实现角度来看是不难的,可以有较简单的DP,O(n^2)
但数据量一大,TLE是必然的.
辅之以二分,可以优化至O(nlogn);
当然从你题目上可以看出,简单形式的也是可以胜任的.
下面这个是O(nlogn);
不懂可以再问,不过实践上你可以向任何一个ACMer或中学生OI选手请教.
#includeiostream
using namespace std;
#define _cp(a,b) ((a)(b))
int ans[501],a[501];
int subseq(int n,int* a,int* ans){
int b[501],p[501],i,l,r,m,ret=0;
for (i=0;in;p[b[l]=i++]=b[l-1],ret+=(lret))
for (m=((l=1)+(r=ret))1;l=r;m=(l+r)1)
if (_cp(a[b[m]],a[i]))
l=m+1;
else
r=m-1;
for (m=b[i=ret];i;ans[--i]=a[m],m=p[m]);
return ret;
}
int main(){
int n,T;cinT;
while(T--cinn){
for (int i=0;incina[i];++i);
int mlen=subseq(n,a,ans);
coutmlenendl;
for (int i=0;imlen;++i)
if(i!=mlen-1)
coutans[i]' ';
else
coutans[i]endl;
coutendl;}
}
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最长递子序列的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java最大连续子序列、java最长递子序列的信息别忘了在本站进行查找喔。