最长递增子序列（Longest Increasing Subsequence，简写 LIS）是动态规划
比较经典的一个问题。

先定义一个dp 数组：dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
最终结果（子序列的最大长度）就是 dp 数组中的最大值。

根据刚才对 dp 数组的定义，dp[i] 的值，也就是以 nums[i] 为结尾的最长递增子序列。

如何通过 dp[0...i-] 的结果推出dp[i]
既然是递增子序列，我们只要找到前面那些结尾比 nums[i]小的子序列，然后把 nums[i] 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。这里可能出现多个取最大那个。

base case。dp 数组应该全部初始化为 1

public static int[] lis(int[] nums){
    int length = nums.length;
    int[] dp = new int[length];
    for (int i=0;i<length;i++) {
        dp[i] = 1;
        for (int j=0;j<i;j++) {
            if (nums[j]<nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return dp;
}