Go语言视频零基础入门到精通

javalearner

所谓子序列，就是在原序列里删掉若干个元素后剩下的序列，以字符串"abcdefg"为例子，去掉bde得到子序列"acfg"，。现在的问题是，给你一个数字序列，你要求出它最长的单调递增子序列的长度（LIS）并输出构成。     设给定序列为 array[]，大小为 n， 最长单调子序列必定以序列array[]中的某一个元素结尾，这是废话。     设lis为以array结尾的最长单调子序列的长度，那么array[]的LIS的长度就是:
max{lis} (0<=i<n)  显然此问题具有最优子结构性质:
  
  
   
   

     
   

     
   
  

  lis[0]=1;
lis[i+1]=max{1,lis[k]+1} (array[i+1]>array[k], k <= i)  即如果array[i+1]大于array[k],那么第i+1个元素可以接在lis[k]长的子序列后面构成一个更长的子序列。
于此同时array[i+1]本身至少可以构成一个长度为1的子序列。

1. import java.util.Scanner;
   
2. public class TestLIS{
   
3.   private  int n;
   
4.   private int array[];
   
5.   private int lis[];
   
6.    public TestLIS(int n,int[] array){
   
7.       this.n=n;
   
8.       this.array=array;
   
9.       lis=new int[n];
   
10.    }
    
11.    public static void main(String[] args) {
    
12.      
    
13.         Scanner in=new Scanner(System.in);
    
14.         
    
15.            int n=in.nextInt();
    
16.            int[] array=new int[n];
    
17.            for(int i=0;i< n;i++){
    
18.                 array[i]=in.nextInt();
    
19.            }  
    
20.          
    
21.           TestLIS tl=new TestLIS(n,array);
    
22.           int maxl=tl.lis();
    
23.          
    
24.           System.out.println("最长单调递增子序列长度："+maxl);
    
25.           System.out.println();
    
26.           System.out.println("最长单调递增子序列构成");
    
27.           int k=tl.max();
    
28.           tl.print(k);
    
29.           System.out.println();
    
30.       
    
31.       
    
32.    }
    
33.   /**
    
34.    * @param args
    
35.    */
    
36.    //求数组最长递增子序列
    
37.   public  int lis()
    
38.   {
    
39.         for(int i =0;i< n;i++)
    
40.         {
    
41.                 lis[i]=1;
    
42.                 for(int j=0;j< i;j++)
    
43.                 {
    
44.                         if(array[j]< array[i]&&(lis[j]+1>lis[i]))
    
45.                           lis[i]=lis[j]+1;
    
46.                        
    
47.                
    
48.                 }
    
49.                
    
50.         }
    
51.         int max=0;
    
52.         for(int k=0;k< lis.length;k++)
    
53.         {
    
54.                // System.out.print(lis[k]+"  ");
    
55.                 if(lis[k]>max)
    
56.                 max=lis[k];
    
57.         }
    
58.        // System.out.println();
    
59.         return max;
    
60.    }
    
61.       //求数组中最大值下标  
    
62.     private int max()  
    
63.     {  
    
64.         int max = lis[0];  
    
65.         int k = 0;  
    
66.         for (int i = 0; i < lis.length; i++)  
    
67.         {  
    
68.             if (max < lis[i])  
    
69.             {  
    
70.                 max = lis[i];  
    
71.                 k = i;  
    
72.             }  
    
73.         }  
    
74.         return k;  
    
75.     }  
    
76. 
    
77.     //输出   
    
78.     public void print(int k)  
    
79.     {      
    
80.         for (int i = k - 1; i >= 0; i--)  
    
81.         {  
    
82.             if (lis[k] == lis[i] + 1 && array[i] <= array[k])  
    
83.             {  
    
84.                 print(i);  
    
85.                 break;  
    
86.             }  
    
87.         }  
    
88.         System.out.print(array[k] + " ");  
    
89.     }  
    
90. }
    

复制代码

运行：
5
1 10 4 9 7
最长单调递增子序列长度：3  最长单调递增子序列构成
1 4 9
  

  
  
   
   

     
   

     
   
  

复制代码

源码下载：http://file.javaxxz.com/2014/12/5/001033359.zip