最长递增子序列（LIS）问题

本文主要是介绍最长递增子序列（LIS）问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

public ArrayList<Integer> LIS(int[] arr)	//获取最长递增子序列{ArrayList<Integer> array = new ArrayList<Integer>();int len = arr.length;if(len==0)	//数组长度为0return array;int[] f = new int[len];	//记录以当前元素作为尾元素的最长递增子序列长度int[] path = new int[len];	//记录以当前元素作为尾元素时，其最长递增子序列的前一个元素索引位置for (int i = 0; i < arr.length; i++) {int max = 0;	//记录arr[0]到arr[i-1]中最长递增子序列最大长度int pos = -1;	//记录以arr[i]作为尾元素的最长递增子序列的前一个元素位置，若不存在，则为-1int min_value = Integer.MAX_VALUE;	//该最长递增子序列是同长度的最长递增子序列中值较小的,/*例如对于数组arr = {1,3,5,2,4,6,7,8}* 其最长递增子序列长度为6，分别为[1,3,5,6,7,8],* 				  [1,3,4,6,7,8],* 				  [1,2,4,6,7,8],* 则选择[1,2,4,6,7,8]，因为从左往右比较发现2<3。* */int j = -1;for (j = 0; j < i; j++) {if((arr[i]>=arr[j]) && (f[j]>max || (f[j]==max && arr[j]<min_value))){pos = j;max = f[j];min_value = arr[j];}}f[i] = max+1;path[i] = pos;}int t = 0;	//查找arr数组中长度最大的最长递增子序列尾元素的索引int fMax = f[0];int min_value = arr[0];for (int i = 1; i < arr.length; i++) {if((f[i]>fMax) || (f[i]==fMax && arr[i]<min_value)){fMax = f[i];min_value = arr[i];t = i;}}Stack<Integer> stack = new Stack<Integer>();while(path[t]!=-1)	//由于是从后往前迭代，得到的是逆序，所以使用栈保存然后再导出得到正序{stack.push(arr[t]);t = path[t];}stack.push(arr[t]);while(stack.isEmpty()==false){array.add(stack.pop());}return array;}

public int LIS(int[] arr){	//贪心法获取最长递增子序列长度ArrayList<Integer> container = new ArrayList<Integer>();for (int i = 0; i < arr.length; i++) {if(container.isEmpty())container.add(arr[i]);else{	int t = Arrays.binarySearch(container.toArray(), arr[i]);//二分查找第一个比arr[i]大的元素位置int x;if(t>=0)	//查找到与arr[i]值相同的元素位置,则往后顺序查找第一个大于arr[i]的元素{x = t+1;while(x<container.size() && container.get(x)==arr[i])x++;}else	//t小于0,t值代表arr[i]应插入（即我们要求的替换）的位置x取反-1，则x=-(t+1)x = -(t+1);if(x==container.size())//不存在比arr[i]大的元素，则直接添加container.add(arr[i]);else	//否则替换arr[x]为arr[i]container.set(x, arr[i]);}}