题解 | #最长上升子序列(二)#

也算是一种动态规划

新建一个数组，单调递增，数组中的数字upVec[i]表示长度为n的最小子序列，数组的长度就是最终子序列的长度。

新来一个元素，如果他大于数组中的所有数字，则插入到末尾， 否则，把第一个大于他的数字变成他。 假设upVec = [1,3,5]， 如果来了7，则变成 [1,3,5,7],如果之后再来了2， 则变成[1,2,5,7]; （表示长度为2的子序列末尾最小值是2，因为他的前面只有1比他小）。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 该数组最长严格上升子序列的长度
     * @param a int整型vector 给定的数组
     * @return int整型
     */
    int LIS(vector<int>& a) {
        vector<int> upVec;
        for (auto it = a.begin(); it != a.end(); it++) {
            auto itVec = lower_bound(upVec.begin(), upVec.end(), *it);
            if (itVec == upVec.end()) {
                upVec.push_back(*it);
            } else {
                *itVec = *it;
            }
        }
        return upVec.size();
    }
};