课程咨询 :186 8716 1620      qq:2066486918

昆明Java培训 > 达内新闻 > 昆明java培训:java实现LIS算法
  • 昆明java培训:java实现LIS算法

    发布:昆明Java培训      来源:达内新闻      时间:2016-09-28

  • 昆明Java培训机构的老师带你一起java实现LIS算法,出操队形问题

    假设有序列:2,1,3,5,求一个最长上升子序列就是2,3,5或者1,3,5,长度都为3。

    LIS算法的思想是:

    设存在序列a。

    ①如果只有一个元素,那么最长上升子序列的长度为1;

    ②如果有两个元素,那么如果a[1]>a[0],则最长上升子序列的长度为2,a[1]为该最长上升子序列的最后一个元素;若a[1]<a[0],则最长上升子序列的长度为1,a[0]和a[1]均为 其最长上升子序列的最后一个元素。

    ③如果由三个元素,那么如果a[2]>a[0],a[2]>a[1],则a[2]可以作为a[0]或者a[1]所在最长上升子序列的最后一个元素。那选择哪一个序列就要看a[0],a[1]哪个所在的序列要更长。

    ④扩展到n个元素,就是看以a[n]为最后一个元素的最长上升子序列的长度是多少。

    定义两个数组,一个是a,一个是b。

    a存放原始数据,b[i]存放的是以a[i]结尾的最长上升子序列的长度。

    代码如下:

    class Lmax{

    public static void Lmax(int[] a,int[] b){

    b[0]=1;                         

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

    int countmax=0;

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

    if(a[i]>a[j]&&b[j]>countmax){

    countmax=b[j];    //记录下元素数值比a[i]小的但是对应子序列最长的子序列长度

    }

    }

    b[i]=countmax+1;         //a[i]对应的最长子序列长度是

    }

    }

    }

    二、出操队形

    题目描述:

    在读高中的时候,每天早上学校都要组织全校的师生进行跑步来锻炼身体,每当出操令吹响时,大家就开始往楼下跑了,然后身高矮的排在队伍的前面,身高较高的就要排在队尾。突然,有一天出操负责人想了一个主意,想要 换一下队形,就是当大家都从楼上跑下来后,所有的学生都随机地占在一排,然后出操负责人从队伍中抽取出一部分学生,使得队伍中剩余的学生的身高从前往后看,是一个先升高后下降的“山峰”形状。据说这样的形状能够 大家带来好运,祝愿大家在学习的道路上勇攀高峰。(注,山峰只有一边也符合条件,如1,1、2,2、1均符合条件)

    输入:

    输入可能包含多个测试样例。

    对于每个测试案例,输入的第一行是一个整数n(1<=n<=1000000):代表将要输入的学生个数。

    输入的第二行包括n个整数:代表学生的身高(cm)(身高为不高于200的正整数)。

    输出:

    对应每个测试案例,输出需要抽出的最少学生人数。

    样例输入:

    6

    100 154 167 159 132 105

    5

    152 152 152 152 152

    样例输出:

    0

    4

    在用LIS来解这道题的时候,可以这样考虑:

    首先从前向后用LIS求一遍以每一个元素结尾的最长上升子序列的长度,然后将数组逆序,再用LIS求一遍以每一个元素结尾的最长上升子序列的长度。

    得到两个数组b1,b2。

    b1,b2对应相加再减去重复的一个,就是最长的'山峰'。

    public class peak {

    public static void main (String[] args)

    {

    int n;

    int re;

    do{

    Scanner in = new Scanner(System.in);

    n = in.nextInt();

    }while(n<0||n>100000);

    int []a = new int[n];                    //原始数组

    int []ar = new int[n];                   //逆序数组

    Scanner in = new Scanner(System.in);

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

    a[i]=in.nextInt();

    }         

    int[] b1 = new int[n];

    @SuppressWarnings("unused")

    int[] b2 = new int[n];

    Lmax.Lmax(a, b1);

    ar=reverse.reverse(a);         

    Lmax.Lmax(ar, b2);             //求解逆序数组的最长上升子序列

    b2=reverse.reverse(b2);        //将逆序数组的最长上升子序列逆序以便和原始数组的最长上升子序列对应相加

    re = result.result(b1, b2);

    System.out.print(re);

    }

    }<br><br><br><br>

    class result{

    public static int result(int[] a,int[] b){

    int max=0;

    int[] c = new int[a.length];

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

    c[i]=a[i]+b[i];

    }

    Arrays.sort(c);

    max=c[c.length-1]-1;       //对应相加最长的再减去重复的一个人

    return a.length-max;

    }

    }

    学Java开发就到昆明达内Java培训班!了解详情请登陆昆明达内Java培训官网(km.Java.tedu.cn)!

    推荐文章

上一篇:java培训:获取从控制台输入的数据的方法

下一篇:使用泛型对java数组扩容

最新开班日期  |  更多

Java--零基础全日制班

Java--零基础全日制班

开班日期:11/30

Java--零基础业余班

Java--零基础业余班

开班日期:11/30

Java--周末提升班

Java--周末提升班

开班日期:11/30

Java--零基础周末班

Java--零基础周末班

开班日期:11/30

  • 网址:http://km .java.tedu.cn      地址:昆明市官渡区春城路62号证券大厦附楼6楼
  • 课程培训电话:186 8716 1620      qq:2066486918    全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56