LIS 最长递增子序列 Java的简单实现

LIS 最长递增子序列 Java的简单实现

今天遇到了一个求最长递增子序列的问题，看了之后就尝试着用java实现了一下，关于什么是最长递增子序列，这里就不在赘述，可以百度或者Google之，以下为实现的代码：

说明：本段代码实现的功能为

（1）随机生成一个有10个元素的数组，然后输出它的最长递增子序列

（2）输出以其中某一个元素为结尾的最长递增子序列的长度

具体的实现思路在注释中已经详细表明了，比较简单，这里就不再赘述

import java.util.Arrays;

import java.util.Random;

public class LIS {

public static void main(String[] args){

System.out.println("generating a random array...");

LIS lis=new LIS();

int[] oldArray=lis.randomArray();

for (int i = 0; i < oldArray.length; i++) {

System.out.print(oldArray[i]+" ");

}

System.out.println();

System.out.println("最长递增子序列的长度为");

lis.lisGet(oldArray);

}

public int[] randomArray(){

Random random=new Random();

int[] randomArray=new int[10];

for (int i = 0; i < 10; i++) {

randomArray[i]=random.nextInt(10);

}

return randomArray;

}

public void lisGet(int[] arrayL ){

int[] lisLength=new int[arrayL.length];//用于记录当前个元素作为最大元素的最长递增序列的长度

for (int i = 0; i < arrayL.length; i++) { //初始化

lisLength[i]=1;

}

int max=1;

for (int i = 1; i < arrayL.length; i++) {

for (int j = 0http://; j

if (arrayL[j]lisLength[i]) {

lisLength[i]=lisLength[j]+1;

}

if (max

max=lisLength[i];

}

}

}

System.out.println(max);

System.out.println("第i个元素结尾时最长递增子序列："+Arrays.toString(lisLength)); //输出数组

}

}

max=lisLength[i];

}

}

}

System.out.println(max);

System.out.println("第i个元素结尾时最长递增子序列："+Arrays.toString(lisLength)); //输出数组

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。