本文共 2367 字，大约阅读时间需要 7 分钟。

������������������������������������

#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 7;
int dp[maxn], pos[maxn], ans[maxn];
int main() {
    memset(dp, 0, sizeof(dp));
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        arr[i] = num;
    }
    if (n == 0) {
        return 0;
    }
    dp[1] = arr[0];
    int len = 1;
    for (int i = 1; i < n; ++i) {
        if (arr[i] > dp[len]) {
            dp[++len] = arr[i];
            pos[i] = len;
        } else {
            int p = lower_bound(dp + 1, dp + 1 + len, arr[i]) - dp;
            dp[p] = arr[i];
            pos[i] = p;
        }
    }
    int t = len;
    for (int i = n - 1; i >= 0; --i) {
        if (len == 0) {
            break;
        }
        if (pos[i] == len) {
            ans[len] = i;
            --len;
        }
    }
    for (int i = 1; i <= t; ++i) {
        cout << arr[ans[i]] << " ";
    }
    return 0;
}
       
      
     
    

������������

������������������������������������������������������������������������������������������������������������������������������������������������������������������������