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

#include <vector>
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();
        vector<int> dp(1, -1), poslen(n);
        for (int i = 0; i < n; ++i) {
            if (arr[i] > dp.back()) {
                dp.push_back(arr[i]);
                poslen[i] = dp.size() - 1;
            } else {
                int pos = lower_bound(dp.begin() + 1, dp.end(), arr[i]) - dp.begin();
                // cout << arr[i] << " " << pos << endl;
                dp[pos] = arr[i];
                poslen[i] = pos;
            }
        }
        int len = dp.size() - 1;
        vector<int> res(len);
        for (int i = n - 1; i >= 0; --i) {
            if (poslen[i] == len) {
                res[--len] = arr[i];
            }
        }
        return res;
    }
};

思路：动态规划。dp数组下标表示当前能求到的最长子序列长度，dp[i]表示在最长子序列长度为i的情况下，序列的最后一个值。

由于本题不仅仅是求长度，还要写出子序列，而只取dp中的元素是不一定能构成最长子序列的。（{1, 3, 4, 2}中最长子序列是{1, 3, 4}，而根据dp得来的序列是{1, 2, 4}）

所以增加一个poslen数组，用来记录以当前元素为最后一个数的最长子序列长度，这样就能在动态规划结束后，反向遍历arr来找到最长子序列中的数。