子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
典型的动态规划。可以想到，到某个位置的最长严格升序子串，可以由前面的某个小于该位置的数的子串长度加1得到。
可以用一个和nums等长的数组来存储到某个位置时符合要求的子串。
以 10,9,2,5,3,7,101,18 为例：
最后的辅助数组应为：0,0,0,1,1,2,3,3（不包含本身）。
动态规划的时间复杂度为O(n^2)
进阶的要求是时间复杂度为：nlog(n)
这个可以利用二分查找来完成，官解看不懂，不写了，下次有机会再看。动态规划代码：
class Solution { public int lengthOfLIS(int[] nums) { int res = 0; // 辅助数组 int[] arr = new int[nums.length]; for (int i = 0; i < nums.length; i ++) { for (int j = 0; j < i; j ++) { // 题目要求的是严格递增，不包括相等。 if (nums[j] < nums[i]) { arr[i] = Math.max(arr[i], arr[j] + 1); res = Math.max(arr[i], res); } } } // 由于我们存储的是到当前位置之前的最长严格递增子串的长度，不包括当前节点，所以我们需要+1处理，使之包含当前节点。 return res + 1; } }
