假设有序列：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算法,出操队形的问题的全部内容了，希望对大家有所帮助，多多支持考高分网~
