這是一道經典動態(tài)規(guī)劃題目,，LIS最長上升子序列問題。

問題描述：給定數(shù)組arr,，返回arr的最長遞增子序列長度,。比如arr = [2，1,，5,，3，6,，4,，8，9,，7],，最長遞增子序列為：[1，3,，4,，8，9],，所以返回這個子序列的長度5,。

本題的暴力搜索方法思路是以arr[0~i]為頭，遍歷整個數(shù)組,，只要有比當前數(shù)大的,，length+1，數(shù)組向后移一位,。每次遍歷結束,，如果變量max小于當前l(fā)ength，令max等于length,。

顯然這樣的遍歷方法重復太多,，效率太低。

動態(tài)規(guī)劃的整體思路是利用空間換時間,。那么針對本題思路如下:

定義數(shù)組dp[n],，n為arr數(shù)組長度,。dp[i]表示把arr[i]當做最后一個數(shù)時，其最長增長子序列的長度,。而dp[0]為第一個數(shù)的最長子序列長度,，自然其結果為1。用下表舉例說明上述例子,。

定義數(shù)組dp[n],，n為arr數(shù)組長度。dp[i]表示把arr[i]當做最后一個數(shù)時,，其最長增長子序列的長度,。而dp[0]為第一個數(shù)的最長子序列長度，自然其結果為1,。用下表舉例說明上述例子,。

也就是說，本題的目的轉換成了,，去找小于arr[i]的arr[0~i-1]其中對應dp值最大那個數(shù)加1即可,。

代碼：

public int getLIS(int[] arr,int n){
    if(arr == null || n <= 0){
        return 0;
    }
    int[] dp = new int[n];
    int length = 0;
    int max = 0;
    dp[0] = 1;
    for(int i = 1; i < n; i++){
        length = 0;
        for(int j = 0; j < i; j++){
            if(arr[j] < arr[i]){
                if(dp[j] > length){
                    length = dp[j];
                }
            }
        }
        dp[i] = length +1;
        if(dp[i] > max){
            max = dp[i];
        }
    }
    return max;
}