题解 | #最长递增子序列# C++ 解法，挺有意思的一道题

题解 | #最长递增子序列#
C++ 解法

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        if (arr.size() == 0) return vector<int>{};
        vector<int> ans(arr.size(), INT_MAX), maxLen(arr.size(), 1);
        ans[0] = arr[0];
        int tail = 1;
        for (int i = 0; i < arr.size(); ++i) {
            int l = 0, r = tail;
            while (l != r) {
                int mid = ((long long)l + r) >> 1;
                if (ans[mid] >= arr[i]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans[l] = arr[i];
            maxLen[i] = l + 1;
            if (l == tail) ++tail;
        }
        --tail;
        while (ans.back() == INT_MAX) {
            ans.pop_back();
        }
        for (int i = arr.size() - 1; i >= 0; --i) {
            if (tail + 1 == maxLen[i]) {
                ans[tail] = arr[i];
                --tail;
            }
        }
        return ans;
    }
};