LIS 最长递增子序列 Java的简单实现
今天遇到了一个求最长递增子序列的问题，看了之后就尝试着用Java实现了一下，关于什么是最长递增子序列，这里就不在赘述，可以百度或者Google之，以下为实现的代码：
说明：本段代码实现的功能为
（1）随机生成一个有10个元素的数组，然后输出它的最长递增子序列
（2）输出以其中某一个元素为结尾的最长递增子序列的长度
具体的实现思路在注释中已经详细表明了，比较简单，这里就不再赘述
importjava.util.Arrays;
importjava.util.Random;
publicclassLIS{
publicstaticvoidmain(String[]args){
System.out.println("generatingarandomarray...");
LISlis=newLIS();
int[]oldArray=lis.randomArray();
for(inti=0;i<oldArray.length;i++){
System.out.print(oldArray[i]+"");
}
System.out.println();
System.out.println("最长递增子序列的长度为");
lis.lisGet(oldArray);
}
publicint[]randomArray(){
Randomrandom=newRandom();
int[]randomArray=newint[10];
for(inti=0;i<10;i++){
randomArray[i]=random.nextInt(10);
}
returnrandomArray;
}
publicvoidlisGet(int[]arrayL){
int[]lisLength=newint[arrayL.length];//用于记录当前个元素作为最大元素的最长递增序列的长度
for(inti=0;i<arrayL.length;i++){//初始化
lisLength[i]=1;
}
intmax=1;
for(inti=1;i<arrayL.length;i++){
for(intj=0;j<i;j++){
if(arrayL[j]<arrayL[i]&&(lisLength[j]+1)>lisLength[i]){
lisLength[i]=lisLength[j]+1;
}
if(max<lisLength[i]){//得到当前最长递增序列的长度以及该子序列的最末元素的位置
max=lisLength[i];
}
}
}
System.out.println(max);
System.out.println("第i个元素结尾时最长递增子序列："+Arrays.toString(lisLength));//输出数组
}
}
以上就是小编为大家带来的LIS最长递增子序列Java的简单实现的全部内容了，希望对大家有所帮助，多多支持毛票票~