最长上升子序列

最长上升子序列(nlogn)

int LIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> vec;
​
    for (int i = 0; i < n; i++) {
        int p = lower_bound(vec.begin(), vec.end(), nums[i]) - vec.begin();  //二分查找，返回大于等于nums[i]的第一个位置
        if (p == vec.size())                                                 //添加进来
            vec.push_back(nums[i]);
        else
            vec[p] = nums[i];  //替换掉
    }
    for (auto it : vec)
        cout << it << " ";
    cout << endl;
    return vec.size();  //返回所维护数组的大小
}

如果求最长不降子序列，需要把lower_bound换成upper_bound