使用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[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;ia[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

class result{
  public static int result(int[] a,int[] b){
    int max=0;
    int[] c = new int[a.length];
    for(int i=0;i

以上就是小编为大家带来的使用java实现LIS算法,出操队形的问题的全部内容了，希望对大家有所帮助，多多支持~