题解 | #最长上升子序列(三)#

先贴上代码，有时间再来注解~

class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    vector<int> LIS(vector<int>& arr) {
        int n = arr.size();
        if (n == 0) {
            return {};
        }
        int maxLen = 0;
        vector<int> tails(n);
        vector<int> maxArr(n);
        for (int i = 0; i < n; i++) {
            int left = 0, right = maxLen - 1;
            while (left <= right) {
                int mid = left + ((right - left) >> 1);
                if (tails[mid] < arr[i]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            tails[left] = arr[i];
            maxArr[i] = left + 1;
            if (left == maxLen) {
                maxLen++;
            }
        }
        
        vector<int> res(maxLen);
        int len = maxLen;
        for (int i = n - 1; i >= 0; i--) {
            if (maxArr[i] == len) {
                res[--len] = arr[i];
            }
        }
        return res;
    }
};