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

遍历数组 ，再遍历dp

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
     public int LIS (int[] arr) {
        // write code here

        int len = arr.length;
        if (arr == null && len == 0){
            return 0;
        }
        int maxLen = 0;
        int[] dp = new int[len];
         Arrays.fill(dp, 1);
//         dp[1] = 1;
        for (int i = 1; i < len; i++) {
            for (int j = i-1; j >=0 ; j--) {
                if (arr[i]> arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
            maxLen = Math.max(maxLen,dp[i]);

        }
        return  maxLen;
    }
}