参考了cornerCao大佬学姐的题解：
https://www.acwing.com/solution/LeetCode/content/287/

题目概览

求一组无序数中的最长上升子序列的长度

输入： [10,9,2,5,3,7,101,18]
输出：4
说明：最长递增子序列为[2,3,7,101]，长度为4，可能有多个可能的最长递增子序列，此题只需要返回长度即可。

题解

    int lengthOfLIS(vector<int>& nums) {   
        // 思路：dp的思路是f[i] = max(f[j] + 1), nums[i]>=nums[j]; O(n^2)
        // 实际上只需要保留同等长度的上升子序列下最后元素最小的值即可, 因为只要每个长度下最小，动态增长或修改子序列，最终的子序列是合法的最长上升子序列。由此，考虑直接构造最优上升子序列, 每步考虑合适的位置插入，因为有序，二分logn, 总时间O(nlogn);
        int n = nums.size();
        if (!n) return 0;

        vector<int> help(n + 1, INT_MAX);
        // help[i]: 严格上升子序列长度为i的最后一个元素的值

        help[0] = INT_MIN;
        for (int i = 1; i <= n; i ++) {
            int l = 0, r = i; 
            // r=i, 最长上升子序列的长度最长为i; 
            // 在[INT_MIN, INT_MAX]中寻找合适的位置
            while (l < r) {
                int mid = l + r >> 1;
                if (help[mid] >= nums[i - 1]) r = mid; // >= 保证严格递增子序列
                // 返回右边性质区间的左端点check(x): x <= nums[mid]; mid为目标替换的位置
                else l = mid + 1;
            }
            help[l] = nums[i - 1];
        }

        while (help[n] == INT_MAX) n --;
        return n;
    }