数组中最长递增子序列问题研究（2）

超、凢脫俗 2022-05-15 01:34 174阅读 0赞

在上一篇文章中，我们知道如何得到一个一维数组的最长递增子序列的长度，但是我们并不知道这个子序列是什么！如何去列举出来一个满足要求的这样一个最长递增子序列呢？

在之前讲述的第二种方法中，我们借助了一个minV数组，这个数组对于接下来的实现是有帮助的。我们从一个数组的第一个元素开始遍历，一直遍历到这个元素对应的lis数组中的值不大于最长递增子序列的长度。我们假设使用current指示想获得的最终最长递增子序列的第current个元素，如如果当前current等于1，则表示接下来想找子序列中的第一个元素。每找完一个就将current加1，寻找下一个元素。对于相同lis值的元素我们还需要做一些判断。下面是具体实现的算法：

public static int lis2(int[] array)
    	{
    		if(array==null||array.length==0)
    			return -1;
    		int len=array.length;
    		int[] lis=new int[len];
    		int maxlength=1;
    		int[] minV=new int[len+2];
    		minV[0]=minArray(array)-1;
    		minV[1]=array[0];
    		Arrays.fill(lis, 1);
    		for(int i=1;i<len;i++)
    		{
    			int j;
    			for(j=maxlength;j>=0;j--)
    			{
    				if(array[i]>minV[j])
    				{
    					lis[i]=j+1;
    					break;
    				}
    			}
    			if(lis[i]>maxlength)
    			{
    				maxlength=lis[i];
    				minV[lis[i]]=array[i];
    			}else if(minV[j]<array[i]&&array[i]<minV[j+1])
    			{
    				minV[j+1]=array[i];
    			}
    		}
    		minV[maxlength+1]=Integer.MAX_VALUE;
    		System.out.println(Arrays.toString(lis));
    		int current=1;
    		for(int i=0;i<lis.length&¤t<=maxlength;i++)
    		{
    			if(lis[i]==current)
    			{
    				if(array[i]>minV[current+1])
    					continue;
    				System.out.print(array[i]+" ");
    				current++;
    			}
    		}
    		System.out.println();
    		return maxlength;
    	}

运行结果如下：

1 2 4 5 7 
    长度为：5
    用时：285272纳秒

如果有更好的方法还请大家指教啊。

上面给出了一种寻找一个最长递归子序列的方法，我们知道，对于一个数组来说，可能还有多个最长递增子序列（这些最长递增子序列的长度肯定相等），我们如何去获得所有的最长递增子序列并将它们全部都列举出来呢？我想了个方法，跟大家分享一下，如果大家有好的方法可以共享一下！

我的思路是：使用递归的方法。我们编写一个能够从某个下标开始寻找子序列中第level个数的函数，例如outputLIS(int level,int index,int\[\] lis,int\[\] array,int\[\] minV)，其中level表示我们要寻找的子序列中的第多少位数字，index表示从那个下标开始寻找，array是原数组，lis存储的是相应元素在最后递增子序列中的可能位置，minV\[i\]存储的是长度为i的最长递增子序列的最大元素的最小值。当然在该方法中我们还要借助另外一个数组信息，这个数组用来标志原数组中的某个元素是否被选中在最长递增子序列中。下面给出具体的算法：

//输出所有最长递归子序列
    	private static void outputLIS(int level,int index,int[] lis,int[] array,int[] minV)
    	{
    		if(level==maxlength+1)
    		{
    			for(int i=0;i<flag.length;i++)
    			{
    				if(flag[i])
    				{
    					System.out.print(array[i]+" ");
    				}
    			}
    			System.out.println();
    			return;
    		}
    		while(lis[index]!=level&&index<array.length)
    			index++;
    		while(index<array.length&&lis[index]<level+1)
    		{
    			if(lis[index]==level&&array[index]<minV[lis[index]+1])
    			{
    				flag[index]=true;
    				outputLIS(level+1,index+1,lis,array,minV);
    				flag[index]=false;
    			}
    			index++;
    		}
    	}

运行结果如下：

1 2 4 5 7 
    -1 2 4 5 7 
    长度为：5
    用时：422708纳秒

接下来我把完整的程序附上供大家参考。lis1只求出最长递增子序列的长度，lis2求出长度并列出一种最长递增子序列，lis3求出长度并列举出所有的最长递增子序列。

package com.application.sample;
    
    import java.util.Arrays;
    import java.util.Iterator;
    import java.util.Stack;
    
    //求一个序列的最长递增子序列
    
    public class LISsample {
    	
    	private static boolean[] flag;
    	private static int maxlength;
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] arr={1,-1,2,-2,4,-3,5,-6,7};
    		long start=System.nanoTime();
    		System.out.println("长度为："+lis1(arr));
    		long end=System.nanoTime();
    		System.out.println("用时："+(end-start)+"纳秒");
    		start=System.nanoTime();
    		System.out.println("长度为："+lis2(arr));
    		end=System.nanoTime();
    		System.out.println("用时："+(end-start)+"纳秒");
    		start=System.nanoTime();
    		System.out.println("长度为："+lis3(arr));
    		end=System.nanoTime();
    		System.out.println("用时："+(end-start)+"纳秒");
    	}
    	
    	public static int lis1(int[] array)
    	{
    		if(array==null||array.length==0)
    			return -1;
    		int len=array.length;
    		int[] lis=new int[len];
    		for(int i=0;i<len;i++)
    		{
    			lis[i]=1;
    			for(int j=0;j<i;j++)
    			{
    				if(array[j]<array[i]&&(lis[j]+1)>lis[i])
    				{
    					lis[i]=lis[j]+1;
    				}
    			}
    		}
    		System.out.println(Arrays.toString(lis));
    		return maxArray(lis);
    	}
    	
    	public static int lis2(int[] array)
    	{
    		if(array==null||array.length==0)
    			return -1;
    		int len=array.length;
    		int[] lis=new int[len];
    		int maxlength=1;
    		int[] minV=new int[len+2];
    		minV[0]=minArray(array)-1;
    		minV[1]=array[0];
    		Arrays.fill(lis, 1);
    		for(int i=1;i<len;i++)
    		{
    			int j;
    			for(j=maxlength;j>=0;j--)
    			{
    				if(array[i]>minV[j])
    				{
    					lis[i]=j+1;
    					break;
    				}
    			}
    			if(lis[i]>maxlength)
    			{
    				maxlength=lis[i];
    				minV[lis[i]]=array[i];
    			}else if(minV[j]<array[i]&&array[i]<minV[j+1])
    			{
    				minV[j+1]=array[i];
    			}
    		}
    		minV[maxlength+1]=Integer.MAX_VALUE;
    		System.out.println(Arrays.toString(lis));
    		int current=1;
    		for(int i=0;i<lis.length&¤t<=maxlength;i++)
    		{
    			if(lis[i]==current)
    			{
    				if(array[i]>minV[current+1])
    					continue;
    				System.out.print(array[i]+" ");
    				current++;
    			}
    		}
    		System.out.println();
    		return maxlength;
    	}
    	
    	public static int lis3(int[] array)
    	{
    		if(array==null||array.length==0)
    			return -1;
    		int len=array.length;
    		flag=new boolean[len];
    		int[] lis=new int[len];
    		int maxlength=1;
    		int[] minV=new int[len+2];
    		minV[0]=Integer.MIN_VALUE;
    		minV[1]=array[0];
    		Arrays.fill(lis, 1);
    //		for(int i=1;i<len;i++)
    //		{
    //			int j;
    //			for(j=lis[i-1];j>0;j--)
    //			{
    //				if(array[i]>minV[j])
    //				{
    //					lis[i]=j+1;
    //					break;
    //				}
    //			}
    //			if(lis[i]>maxlength)
    //			{
    //				maxlength=lis[i];
    //				minV[lis[i]]=array[i];
    //			}else if(minV[j]<array[i]&&array[i]<minV[j+1])
    //			{
    //				minV[j+1]=array[i];
    //			}
    //		}
    		for(int i=1;i<len;i++)
    		{
    			int j;
    			for(j=maxlength;j>=0;j--)
    			{
    				if(array[i]>minV[j])
    				{
    					lis[i]=j+1;
    					break;
    				}
    			}
    			if(lis[i]>maxlength)
    			{
    				maxlength=lis[i];
    				minV[lis[i]]=array[i];
    			}else if(minV[j]<array[i]&&array[i]<minV[j+1])
    			{
    				minV[j+1]=array[i];
    			}
    		}
    		System.out.println(Arrays.toString(lis));
    		minV[maxlength+1]=Integer.MAX_VALUE;
    		System.out.println(Arrays.toString(minV));
    		LISsample.maxlength=maxlength;
    		outputLIS(1,0,lis,array,minV);
    		return maxlength;
    	}
    	
    	//输出所有最长递归子序列
    	private static void outputLIS(int level,int index,int[] lis,int[] array,int[] minV)
    	{
    		if(level==maxlength+1)
    		{
    			for(int i=0;i<flag.length;i++)
    			{
    				if(flag[i])
    				{
    					System.out.print(array[i]+" ");
    				}
    			}
    			System.out.println();
    			return;
    		}
    		while(lis[index]!=level&&index<array.length)
    			index++;
    		while(index<array.length&&lis[index]<level+1)
    		{
    			if(lis[index]==level&&array[index]<minV[lis[index]+1])
    			{
    				flag[index]=true;
    				outputLIS(level+1,index+1,lis,array,minV);
    				flag[index]=false;
    			}
    			index++;
    		}
    	}
    	
    	private static int minArray(int[] array)
    	{
    		int result=array[0];
    		for(int i=1;i<array.length;i++)
    		{
    			if(array[i]<result)
    				result=array[i];
    		}
    		return result;
    	}
    	
    	private static int maxArray(int[] array)
    	{
    		int result=array[0];
    		for(int i=1;i<array.length;i++)
    		{
    			if(array[i]>result)
    				result=array[i];
    		}
    		return result;
    	}
    }

整体的运行结果如下所示：

[1, 1, 2, 1, 3, 1, 4, 1, 5]
    长度为：5
    用时：360476纳秒
    [1, 1, 2, 1, 3, 1, 4, 1, 5]
    1 2 4 5 7 
    长度为：5
    用时：433169纳秒
    [1, 1, 2, 1, 3, 1, 4, 1, 5]
    [-2147483648, -6, 2, 4, 5, 7, 2147483647, 0, 0, 0, 0]
    1 2 4 5 7 
    -1 2 4 5 7 
    长度为：5
    用时：451083纳秒

大家有什么意见和好的方法可以说说，谢谢！转载请注明出处。