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

五菱

求数组中最长递增子序列的长度：

如：在序列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的子序列。
根据上面的分析，就可以得到代码清单：



public class TestLIS{
  
   public static void main(String args[]){
    int a[]={1,-1,2,-3,4,-5,6,-7};
     System.out.println(lis(a));
   }
  /**
   * @param args
   */
   //求数组最长递增子序列
  public static int lis(int [] array)
  {
    Integer []lis = new Integer[array.length];
    for(int i =0;i< array.length;i++)
    {
        lis=1;
        for(int j=0;j< i;j++)
        {
            if(array[j]< array&&(lis[j]+1>lis))
            lis=lis[j]+1;
        }
    }
    int max=0;
    for(int k=0;k< lis.length;k++)
    {
        if(lis[k]>max)
        max=lis[k];
    }
    return max;
   }
}