题解 | #最长上升子序列(一)#

最值问题的求解方法适合使用动态规划思想（穷举）解决，把一个四个长度的数组问题拆分为一个长度的数组，两个长度的数组，三个长度的数组，四个长度的数组问题，通过分别求解低长度的数组问题的解找到原始长度数组问题的解。

在求解过程中定义一个与原数组长度等长的数组用来记录不同数组长度的问题的解。

public class Solution {
    public int LIS (int[] arr) {
        if(null==arr || arr.length==0){
            return 0;
        }
        int[] db=new int[arr.length];
        for(int i=0;i<arr.length;i++){
            db[i]=1;
            for(int j=0;j<i;j++){
                if(arr[j]<arr[i]){
                    if(db[j]+1>db[i]){
                        db[i]=db[j]+1;
                    }
                }
            }
        }
        Arrays.sort(db);
        return db[db.length-1];
    }
}