链接
注意： 这里的子序列可以不连续 ！
思路：动态规划 （dp table）
模板：
动态规划的核?设计思想是数学归纳法;
如想证明?个数学结论，那么我们 先假设这个结论在 k < n 时成?，然后根据这个假设，想办法推导证明出 k = n 的时候此结论也成?。如 果能够证明出来，那么就说明这个结论对于 k 等于任何数都成?。
设计动态规划算法，不是需要?个 dp 数组吗？可以假设 dp[0…i-1] 都已经被算出来 了，然后问：怎么通过这些结果算出 dp[i]？
dp数组的定义：dp[i] 表示以 nums[i] 这个数结尾的最长递增?序列的长度；
base case：dp[i] 初始值为 1，因为以 nums[i] 结尾的最?递增?序列起 码要包含它??。
根据这个定义，最终数组的结果（?序列的最??度）应该是 dp 数组中的最?值：
用for遍历每个元素作为结尾对应的最大自增子序列的长度，选出最大；
注意：并不是 i 越大，其子序列长度就越大 ！
假设已经知道了 dp[0…4] 的所有结果，如何通过这些已知结果推出 dp[5] ？
如：
nums[5] = 3，既然是找递增?序列，只要找到前面那些结尾比 3 小的子序列，然后把 3 接到这些子序列末尾，就可以形成?个新的递增子序列，?且这个新的子序列长度加?。
nums[5] 前?有哪些元素小于 nums[5]？用for 循环比较?波就能把这些元素找出来。
以这些元素为结尾的最?递增?序列的?度是多少？回顾?下我们对 dp 数组的定义，它记录的正是以每个元素为末尾的最?递增?序列的?度。
例中nums[0] 和 nums[4] 都是小于 nums[5] 的，然后对比 dp[0] 和 dp[4] 的值，我们 让 nums[5] 和更长的递增?序列结合，得出 dp[5] = 2+1=3 ；
总结：
1.明确 dp 数组的定义。这?步对于任何动态规划问题都很重要，如果不得当或者不够清晰，会阻碍之后的步骤。
2.根据 dp 数组的定义，运?数学归纳法的思想，假设 dp[0…i-1] 都已知，想办法求出 dp[i]，?旦这 ?步完成，整个题目基本就解决了。
Java实现：
dp定义是 dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度；
状态就是dp数组的索引/值
class Solution {
public int lengthOfLIS(int[] nums) {
// 一个元素对应一个子序列长度，所以不需要再加 1
int dp[]=new int[nums.length];
Arrays.fill(dp,1); // 求最大，初始化为小
for(int i=0;i<nums.length;i++){ //遍历共 nums.length种状态
for(int j=0;j<i;j++){ // 遍历结尾元素之前的所有元素 即0~ k-1
// 遍历所有 小于结尾元素的 j , 并选出所有j中子序列长度最长的，再加1就是结果！
if(nums[i]>nums[j]){ // 当 k-1 < k，满足递增条件 ,遍历j更新dp[i]
dp[i]=Math.max(dp[i],dp[j]+1); // 求出 k 对应的值： 0~j（k-1）最大的+1即dp[i]，更新dp[i]
}
}
}
int res=-1;
for(int i=0;i<nums.length;i++){
res=Math.max(res,dp[i]);
}
return res;
}
}