题解 | #最长递增子序列#

贪心算法，遍历数组arr，每次都取尽量长的递增子序列，保存在result中；数组max_len用于保存arr[0,i]的元素中小于等于arr[i]的元素的个数。最后根据等式max_len[i]==j选择最终的结果，表示递增子序列的第j个元素应该这么选：它正好就是arr数组中的元素arr[i]，满足arr[i]的前面有j个元素小于等于arr[i]（也就是说此arr[i]是arr数组中的第j小元素）。

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        vector<int> result{};
        vector<int> max_len{}; //保存arr[0,i]中小于等于arr[i]的个数
        if(arr.empty()) return result;
        result.push_back(arr[0]);
        max_len.push_back(1);
        for(int i=1;i<arr.size();i++){
            if(arr[i]>result.back()){
                result.push_back(arr[i]);
                max_len.push_back(result.size());
            }
            else{
                int pos=lower_bound(result.begin(), result.end(), arr[i]) - result.begin();
                result[pos]=arr[i];
                max_len.push_back(pos+1);
            }
        }
        for(int i=arr.size()-1,j=result.size();j>0;i--){
            if(max_len[i]==j){
                result[--j]=arr[i];
            }
        }
        return result;
    }
};