假设有序列：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[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