简单编程题目连载（九）

这是一道经典动态规划题目，LIS最长上升子序列问题。

问题描述：给定数组arr，返回arr的最长递增子序列长度。比如arr = [2，1，5，3，6，4，8，9，7]，最长递增子序列为：[1，3，4，8，9]，所以返回这个子序列的长度5。

本题的暴力搜索方法思路是以arr[0~i]为头，遍历整个数组，只要有比当前数大的，length+1，数组向后移一位。每次遍历结束，如果变量max小于当前length，令max等于length。

显然这样的遍历方法重复太多，效率太低。

动态规划的整体思路是利用空间换时间。那么针对本题思路如下:

定义数组dp[n]，n为arr数组长度。dp[i]表示把arr[i]当做最后一个数时，其最长增长子序列的长度。而dp[0]为第一个数的最长子序列长度，自然其结果为1。用下表举例说明上述例子。

定义数组dp[n]，n为arr数组长度。dp[i]表示把arr[i]当做最后一个数时，其最长增长子序列的长度。而dp[0]为第一个数的最长子序列长度，自然其结果为1。用下表举例说明上述例子。

数组	1	2	3	4	5	6	7	8	9
arr	2	1	5	3	6	4	8	9	7
dp	1	1	2	2	3	3	4	5	4

也就是说，本题的目的转换成了，去找小于arr[i]的arr[0~i-1]其中对应dp值最大那个数加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;
}