题解 | #最长递增子序列#（一个数组记录查找最长上升子序列的过程，后面较小值可能覆盖结果，需要记录值并回溯）

转载大佬&自己增加解释

class Solution {
public:
    vector<int> LIS(vector<int>&amp; arr) {
        vector<int> res; // 贪心下，用res数组存储最长上升子序列
        vector<int> maxLen;// maxLen[i]:加入arr[i]元素的最大长度。
        if (arr.size() &lt; 1) return res;
        res.emplace_back(arr[0]);  // emplace_back(val)作用同push_back，效率更高
        maxLen.emplace_back(1);
        for (int i = 1; i &lt; arr.size(); ++i) { 
            if (arr[i] &gt; res.back()) {
                res.emplace_back(arr[i]);  // 大于res中保存上升子序列的最后一个元素。 
                maxLen.emplace_back(res.size()); 
                //res记录且maxLen记录加入该元素时最大上升长度。 
            } else { 
                // 它的作用是返回有序数组begin..end中第一个大于等于val的元素的迭代器
                res[pos] = arr[i]; // 将arr[i]元素加入满足第一个大于它的元素处，此处贪心
        //不影响后续判断，在求最长上升子序列中，中间元素可以替换，记录后续情况。arr[i]替换res[pos]的原因
                maxLen.emplace_back(pos+1); // 记录以arr[i]结尾的最长长度。
            }
        }
        // 第二步：填充最长递增子序列，贪心时后面添加元素可能覆盖正确的升上子序列
        for (int i = arr.size()-1, j = res.size(); j &gt; 0; --i) {
            if (maxLen[i] == j) { 
         // 当以arr[i]结尾的最长长度是满足当前元素前最大上升子序列长度时，
         // res中的位置 替换成 arr[i] ，这样从前往后执行最后会得到序列最小的最长上升子序列。
                res[--j] = arr[i]; //j：是从1到res.size(),减1才对应在res中的位置
            }
        }
        return res;
    }
};