最长递增子序列
给你一个整数数组 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)) 吗?
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence
tips:
动态规划题目的核心就是找出大规模与小规模之间的关系。
拿示例1来说，A = [10, 9, 2, 5, 3, 7, 101, 18]
比 A 规模更小的是B = [10, 9, 2, 5, 3, 7, 101] ，若知道 B 中的最长递增子序列的长度 4 后能否在此基础上快速推断出A的最长子序列？显然不能。因为我们不知道 A比 B 多出的尾部元素 18是否可以加到某个现有最长子序列的尾部，形成更长的子序列。
不管是自顶向下的函数递归法，还是自底向上的数组法（也叫dp数组法，动态规划 dynamic programming，简称dp），我们最最开始应该做的就是明确 函数（返回值）含义 或 dp数组中下标i与值dp[i]的含义。
我们通常可以在定义中添加一些限制条件，便于我们找出不同规模之间的递推关系（动态转移方程）。
对比这两种定义：
| 是否添加限制 | 定义 |
|---|---|
| 否 | dp[i]：数组nums[0:i+1] （python切片前闭后开）中最长递增子序列的长度 |
| 是 | dp[i]：数组nums[0:i+1] 中以nums[i] 这个数结尾的最长递增子序列的长度 |
尝试寻找递推关系
nums = [10, 9, 2, 5, 3, 7, 101, 18]
不加限制：
| dp[0] | dp[1] | dp[2] | dp[3] | dp[4] | dp[5] | dp[6] | dp[7] |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 |
这个过程中，dp[大] 的计算不能依赖已知的dp[小]。不能依赖即不能递推，所以这是糟糕的定义