LIS

求一组数的lis

class Solution {
public:
    //low[i]代表长度为i的lis的结尾的最小值
    int lengthOfLIS(vector<int>& a) {
        int n = a.size();
        int cnt = 0;
        vector<int> low(n + 1), f(n);
        for(int i = 0; i <= n; i++) {
            low[i] = -1;
        }
        for(int i = 0; i < n; i++) {
            int t = lower_bound(low.begin() + 1, low.begin() + cnt + 1, a[i]) - low.begin();
            f[i] = t;
            cnt = max(cnt, t);
            low[t] = a[i];
        }
        return cnt;
    }
};