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

class Solution {
public:
    /**
     * return the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // write code here
        // 第一步：利用贪心求最长递增子序列长度---目的是求出以当前位置为结尾的最长子序列，以及以当前位置为结尾的最小一个数字（放到res里，比如12413，3就是说当前以3为结尾的最长长度为2，而且以他为结尾的话最小为3，即长度为2的子序列最小末尾值为3）实际上，res是辅助，maxlen才是主角，maxlen记录了每个长度，而且通过res的操作，我们可以知道从后向前看，maxlen实际上是存储了每一个相同长度的最小值。res不重要，我们不要太想res，res就是为了给maxlen带来长度而出现的。
        vector<int> res;
        vector<int> maxLen;
        if (arr.size() < 1) return res;
        res.emplace_back(arr[0]);  // 注：emplace_back(val)作用同push_back，效率更高
        maxLen.emplace_back(1);
        for (int i = 1; i < arr.size(); ++i) {
            if (arr[i] > res.back()) {
                res.emplace_back(arr[i]);
                maxLen.emplace_back(res.size());
            } else {
                // lower_bound(begin, end, val)包含在<algorithm>中
                // 它的作用是返回有序数组begin..end中第一个大于等于val的元素的迭代器
                int pos = lower_bound(res.begin(), res.end(), arr[i]) - res.begin();
                res[pos] = arr[i];
                maxLen.emplace_back(pos+1);
            }
        }
        // 第二步：填充最长递增子序列（但是之前那个res肯定不一定是结果，我们希望将res的值进行更新，就是每一位都是最小值，而且符合前后位置的限制，就是得从res.size()开始，如果目前maxlen的值和size相等，那么就说明应该是目前的值是最小的，更新到res进去，然后找maxlen为size-1的位置）
        for (int i = arr.size()-1, j = res.size(); j > 0; --i) {
            if (maxLen[i] == j) {
                res[--j] = arr[i];
            }
        }
        return res;
    }
};