题解 | #最长递增子序列#贪心+二分

//1.理解贪心算法使用
//2.maxLen数组的作用--找到字典序递增子序列
//3.二分查找
//Leetcode上最长递增子序列求长度+牛佬“华科不平凡”的maxLen数组恢复字典序

class Solution {
public:
    //找到第一个比value大的值
    int binarySearch(vector<int>&res,int value){
        int left=0;
        int right=res.size()-1;

        //如果没找到就返回位置0，因为这时res的值全部大于value，需要替换第一个
        int pos=0;
        while(left<=right){
            int middle=left+((right-left)>>1);

            if(res[middle]>value){
                pos=middle;
                right=middle-1;
            }
            else{
                left=middle+1;
            }   
        }
        //没找到就返回pos==0
        return pos;

    }

    vector<int> LIS(vector<int>& arr) {
        if(arr.empty()) return {};

        vector<int> res;               //存放递增子序列
        vector<int> maxLen;            //存放当前元素在子序列最后一位时子序列长度

        res.emplace_back(arr[0]);
        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{
                int pos=binarySearch(res,arr[i]);
                res[pos]=arr[i];
                maxLen.emplace_back(pos+1);

            }

        }
        //从后往前更新最长递增子序列
        for(int i=arr.size()-1,j=res.size();j>0;--i){
            if(maxLen[i]==j){
                res[--j]=arr[i];
            }    
        }

        return res;

    }
}