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]对应的最长子序列长度是		}					}	}

原标题：java实现LIS算法，出操队形问题

关键词：JAVA