给你一个整数数组 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
• $-10^4$ <= nums[i] <= $10^4$

进阶：

你能将算法的时间复杂度降低到 $O(nlog(n))$ 吗?

题解1 DP $O(n^2)$

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp(nums.size(), 1);int maxN = INT_MIN;/**dp[i] : i处数值对应的最长子序列长度**/for(int i = 1; i < nums.size(); i++){    for(int j = 0; j < i; j++){if(nums[i] > nums[j])dp[i] = max(dp[i], dp[j]+1);}maxN = max(maxN, dp[i]);}return maxN == INT_MIN ? 1 : maxN;}
};

题解2 贪心+二分搜索（ref. from Leetcode）$O(nlog(n))$

“从左到右（序列顺序），维护一个每个元素尽可能小的LIS备选集合S”

每个元素尽可能小，这样更可能在末尾加上一个新的值，构成一个更大的LIS

只增加（add）和替换（swap），因此完成遍历后S的长度一定等于LIS的长度,部分元素可能被你替换掉了，所以在整个遍历过程中，这个集合S可能并不是LIS本身,尽管如此，LIS的元素一定曾出现在S中（但可能在遍历过程中被swap覆盖掉了）

鼓掌！！这个思想好棒

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(1 == nums.size()) return 1;// p[i]: 长度为i的最长上升子序列的末尾元素最小值vector<int> p(nums.size()+1, 0);int len = 1;p[len] = nums[0];for(int i = 1; i < nums.size(); i++){if(nums[i] > p[len]){len ++;p[len] = nums[i];}else{// 在i位置不用遍历得到dp值// 长度=len+1的子序列的最小值 > nums[i]，为了保持p的递增，需要修改某个位置的值// 用二分找到最近的j, 满足p[j] < nums[i] < p[j+1]// s.t. p[j+1] = nums[i];// 如果找不到, 说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0int left = 1;int right = len;int pos = 0;// 最希望的是改p[len], 所以判断条件 有 =// 实际上是想不用遍历，用二分检查一遍 nums[i]是不是大于len+1情况里的倒数第二个最大的数吧while(left <= right){int mid = (left+right) >> 1;// 找到了jif(nums[i] > p[mid]){pos = mid;left = mid+1;}  else{right = mid-1;}}p[pos + 1] = nums[i];}}return len;}
};