最长递增子序列和最长不降子序列

前言：最长递增子序列和最长不降子序列的代码模板

int LIS(vector a) {
    vector dp;
    for(int x : a) {
        auto pos = upper_bound(dp.begin(), dp.end(), x); // < : lower, <= : upper
        if(pos == dp.end()) 
        	dp.push_back(x);
        else 
        	*pos = x;
    }
    return dp.size();
}

注意: 代码中的 < 代表递增子序列，需要使用 lower_bound 函数，而 <= 则代表不降子序列，需要使用 upper_bound 函数.