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

javalearner

求数组中最长递增子序列的长度： 如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。其长度为4。
假设在目标数组array[]的前i个元素中，最长递增子序列的长度为LIS。那么，

LIS[i+1]=max{1,LIS[k]+1},array[i+1]>array[k],for any k <= i

即如果array[i+1]大于array[k],那么第i+1个元素可以接在LIS[k]长的子序列后面构成一个更长的子序列。于此同时array[i+1]本身至少可以构成一个长度为1的子序列。
根据上面的分析，就可以得到代码清单：

1. public class TestLIS{
   
2.   
   
3.    public static void main(String args[]){
   
4.     int a[]={1,-1,2,-3,4,-5,6,-7};
   
5.      System.out.println(lis(a));
   
6.    }
   
7.   /**
   
8.    * @param args
   
9.    */
   
10.    //求数组最长递增子序列
    
11.   public static int lis(int [] array)
    
12.   {
    
13.         Integer []lis = new Integer[array.length];
    
14.         for(int i =0;i< array.length;i++)
    
15.         {
    
16.                 lis[i]=1;
    
17.                 for(int j=0;j< i;j++)
    
18.                 {
    
19.                         if(array[j]< array[i]&&(lis[j]+1>lis[i]))
    
20.                         lis[i]=lis[j]+1;
    
21.                 }
    
22.         }
    
23.         int max=0;
    
24.         for(int k=0;k< lis.length;k++)
    
25.         {
    
26.                 if(lis[k]>max)
    
27.                 max=lis[k];
    
28.         }
    
29.         return max;
    
30.    }
    
31. }
32. 
    
33.                         

复制代码

  


源码下载：http://file.javaxxz.com/2014/11/30/000657109.zip