最长递增子序列

$O(nlogn)$

可以求出子序列

C++ 代码

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        // 简单的线性dp
        int n = arr.size();

        vector<int> f(n+1); // 记录对应长度对应的数
        vector<int> maxlen;
        int len = 0;
        for(int i = 0; i < n; i ++)
        {
            int l = 0, r = len;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(f[mid] < arr[i]) l = mid; // 可能就是这个数比他小
                else r = mid - 1;
            }
            len = max(len, r + 1);
            f[r+1] = arr[i];
            maxlen.push_back(r+1); // 加入一个长度
        }
        // 贪心的方法来确定最长序列
        int tem = len;
        for(int i = n - 1; len > 0; i --)
        {
            if(maxlen[i] == len)
                f[--len] = arr[i]; 
        }
        return vector<int>(f.begin(), f.begin()+tem);
    }
};