数组中最长递归子序列问题研究（1）

矫情吗；* 2022-05-15 01:07 147阅读 0赞

问题：对于一个一维数组，求这个一维数组中的最长递增子序列的长度。

例如：如果一维数组为\{1,-1,2,-3,4,-5,6,-7\}，则得到的一个最长递增子序列为\{1,2,4,7\}，长度为4。

下面是java语言编写的两种实现方法。

package com.application.sample;
    
    import java.util.Arrays;
    
    //求一个序列的最长递增子序列
    
    public class LISsample {
    
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] arr={1,4,2,3,5,8,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+1];
    		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];
    			}
    		}
    		System.out.println(Arrays.toString(lis));
    		return maxlength;
    	}
    	
    	public static int lis3(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+1];
    		minV[0]=minArray(array)-1;
    		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];
    			}
    		}
    		System.out.println(Arrays.toString(lis));
    		return maxlength;
    	}
    	
    	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, 2, 2, 3, 4, 5, 5]
    长度为：5
    用时：332238纳秒
    [1, 2, 2, 3, 4, 5, 5]
    长度为：5
    用时：122968纳秒
    [1, 2, 2, 3, 4, 5, 5]
    长度为：5
    用时：89809纳秒

从运行结果来看，也验证了在编程之美中关于这个问题的时间复杂度的分析。