最长递增子序列（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;
}
