题目链接：最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

方法一：动态规划

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int f[2550];
        f[0] = 1;
        int ans = 1;
        for (int i = 1;i < nums.size();i++) {
            f[i] = 1;
            for (int j = 0;j < i;j++) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i],f[j] + 1);
                    ans = max(ans,f[i]);
                }
            }
        }
        return ans;
    }
};

方法二：贪心+二分

int first_ge(const vector<int>& a, int x) {
    int l = 0, r = (int)a.size(); // [l, r)
    while (l < r) {
        int m = l + (r - l) / 2;
        if (a[m] >= x) r = m;
        else l = m + 1;
    }
    return l; // 第一个 >= x 的位置（可能等于 a.size()）
}

int lengthOfLIS(vector<int>& nums) {
    vector<int> tails;
    for (int x : nums) {
        int i = first_ge(tails, x);
        if (i == (int)tails.size()) tails.push_back(x);
        else tails[i] = x;
    }
    return (int)tails.size();
}