给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1提示：
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶：
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
解题思路：递归 -> 记忆化搜索
如果我们要直接递归进去求整个数组的最长递增子序列的长度的话，其实不好搞，但是如果我们在主函数中用一个 for 循环，遍历每个元素，让每个元素都作为起点获取其最长递增子序列的长度，然后再记录下最长的那个就行了，这样子相对来说好办一些！
也就是说递归函数 dfs() 需要传入一个当前元素的起点 pos，然后负责帮我们拿到以该 pos 为起点的最长递增子序列的长度，所以它的返回值类型是 int。
至于递归函数体，其实也是一个循环，因为我们在主函数中以某个元素为起点进行递归之后，其实到了下一层中就是找到符合递增的元素，然后继续递归求其最长子序列长度，以此类推，我们只需要关注一层的细节即可！如下图简单所示：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int ret = 0;
for(int i = 0; i < nums.size(); ++i)
ret = max(dfs(nums, i), ret); // 获取以i元素开头得到的最长子序列，然后记录最长的那个
return ret;
}
int dfs(vector<int>& nums, int pos)
{
int ret = 1;
for(int i = pos + 1; i < nums.size(); ++i)
{
// 遍历pos后面的所有位置，看看谁能加到pos这个元素的后面
if(nums[pos] < nums[i])
ret = max(ret, dfs(nums, i) + 1);
}
return ret;
}
}; 这种写法毋庸置疑，是会超时的，因为从上面的递归树就能看出，虽然没画全，但是可以想象出其中是有很多重复的子树的，所以我们可以用记忆化搜索了解决问题，就是添加一个备忘录，具体步骤这里不再赘述，直接上代码：
class Solution {
private:
int memory[2501] = { 0 }; // 一维数组作为备忘录，初始化为0即可
public:
int lengthOfLIS(vector<int>& nums) {
int ret = 0;
for(int i = 0; i < nums.size(); ++i)
ret = max(dfs(nums, i), ret); // 获取以i元素开头得到的最长子序列，然后记录最长的那个
return ret;
}
int dfs(vector<int>& nums, int pos)
{
// 在进入函数之前，判断是否已经存在过备忘录中了
if(memory[pos] != 0)
return memory[pos];
int ret = 1;
for(int i = pos + 1; i < nums.size(); ++i)
{
// 遍历pos后面的所有位置，看看谁能加到pos这个元素的后面
if(nums[pos] < nums[i])
ret = max(ret, dfs(nums, i) + 1);
}
// 离开函数之前，将当前结果计入备忘录
memory[pos] = ret;
return ret;
}
}; 可以看到，代码中只改动了三处地方：创建备忘录、添加结果到备忘录、检查备忘录！瞬间就跑通了，还干掉了 80% 的解法！
