最长递增子序列(LIS longest-increment-subsequence)问题

1.问题描述

给定一个数组，就数组最长递增子序列(子序列可以不连续)

2.解法

非常经典的动态规划问题，算法的时间复杂为O(n^2)，空间复杂度为O(n)。
关键是结果数组dp[i]怎么计算呢？
每次遍历所有j<i中数组的元素，判断array[j]是否小于array[i]。
如果是，检查dp[i]与dp[j]+1的大小，并且更新dp[i]。

    public static int lis() {
        int[] nums = {1, 3, 6, 2, 3, 4};
        int len = nums.length;
        int[] dp = new int[len];
        int result = 0;
        for(int i=0; i<len; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = dp[i] > dp[j] + 1 ? dp[i] : dp[j] + 1;
                }
            }
            result = dp[i] > result ? dp[i] : result;
        }

        return result;
    }