LIS

题目：这是一个经典的LIS(即最长上升子序列)问题，请设计一个尽量优的解法求出序列的最长上升子序列的长度。给定一个序列A及它的长度n(长度小于等于500)，请返回LIS的长度。

思路：经典dp,维护一个一维数组dp[],里面每个值代表必须以这个索引对应的序列值结尾的最长子序列，然后在dp[]里找出最大的即可。比如数组[1,4,2,3,5],生成dp[5],dp[0]先置1，dp[1]就是找4之前的比4小的那些数对应的最大dp数组的值，即1比4小，而且只有一个，所以对应dp值是最大的，即dp[0]=1,所以dp[1]=dp[0]+1=2;  再来看dp[2],2之前只有1比2小，所以dp[2]=dp[0]+1=2;  dp[3]就找3前面的比3小的数，即1和2，对应dp[0]=1,dp[2]=2,所以选择dp[2],故dp[3]=dp[2]+1=3;....一次类推，最后找出dp数组中的最大值即为所求

 public int getLIS(int[] A, int n) {
       int[] dp = new int[n];
       int res=0;
        dp[0] = 1;
        for(int i=1;i<n;i++){
            int max=0;//找比i小的值里对应dp最大的
            for(int j=0;j<i;j++){
                if(A[j]<A[i]){
                    if(max<dp[j])
                        max=dp[j];
                }
            }
            dp[i]=max+1;
        }
        //找dp中的最大值
       for(int i=0;i<n;i++){
           if(res<dp[i])
               res=dp[i];
       }
        return res;
    }