题解 | #最长上升子序列（三）#

```cpp

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.empty()) {
        return arr;
      }
      
      std::vector<int> dp(arr.size() + 1, -1), h(arr.size());
      int len = 1;
      dp[len] = arr[0];
      h[0] = 1;
      
      for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > dp[len]) {
          dp[++len] = arr[i];
          h[i] = len;
        } else {
          int left = 1, right = len, pos = 0;
          while (left <= right) {
            int mid = (left + right) / 2;
            if (dp[mid] < arr[i]) {
              pos = mid;
              left = mid + 1;
            } else {
              right = mid - 1;
            }
          }
          dp[pos + 1] = arr[i];
          h[i] = pos + 1;
        }
      }
      
      std::vector<int> res(len);
      
      for (int i = arr.size() - 1; i >= 0; --i) {
        if (h[i] == len) {
          res[--len] = arr[i];
        }
      }
      
      return res;
    }
};
```