题目：300. 最长上升子序列

动态规划思路：

遍历计算，计算过的长度使用数组dp[]记录，使用计算过的结果计算新位置的长度

解体逻辑：

定义dp[]，存储arr以对应元素为尾的字串长度
		arr = {1,4,6,79,4}
		dp  = {1,2,3,4 ,2}
即：以6结尾的递增字串长度为3：{1,4,6}
当 arr[3] >  arr[2] 时， dp[3] = Max(dp[0]~dp[2]) + 1;
当 arr[3] <= arr[2] 时， dp[3] = Max(dp[0]~dp[2]);

java代码：

    public static int findLenght(int[] arr){
        if(arr == null || arr.length < 1){
            return 0;
        }
        // 存储arr以对应元素为尾的字串长度
        int[] dp = new int[arr.length];
        int maxLength = 1;
        int posLength = 0;
        dp[0] = 1;
        // 遍历nums
        for(int pos = 1 ; pos < arr.length ; pos++){
            // pos位置以pos结尾上升子序列长度
            posLength = 1;
            for(int j = 0 ; j < pos ; j ++){
                if(arr[pos] > arr[j]){
                    posLength = Math.max(posLength, dp[j]);
                }
            }
            dp[pos] = posLength + 1;
            maxLength = Math.max(dp[pos], maxLength);
            System.out.println(Arrays.toString(dp));
        }
        return maxLength;
    }

    public static void main(String[] args) {
        int[] nums = {1,4,6,79,4,2,2,67,9};
        System.out.println(findLenght(nums));
    }

输出：

[1, 2, 0, 0, 0, 0, 0, 0, 0]
[1, 2, 3, 0, 0, 0, 0, 0, 0]
[1, 2, 3, 4, 0, 0, 0, 0, 0]
[1, 2, 3, 4, 2, 0, 0, 0, 0]
[1, 2, 3, 4, 2, 2, 0, 0, 0]
[1, 2, 3, 4, 2, 2, 2, 0, 0]
[1, 2, 3, 4, 2, 2, 2, 4, 0]
[1, 2, 3, 4, 2, 2, 2, 4, 4]
4