LIS - Dãy con tăng dài nhất (Sol 1)

//LIS - Dãy con tăng dài nhất
#include <bits/stdc++.h>
#define int64_t long long
using namespace std;

const int N = 1e5 + 5;

int n;
int a[N];

int cache[N];
int sizer, b[N];

void DP() {
   for(int i = 1; i <= n; i++) {
      cache[i] = lower_bound(b + 1, b + sizer + 1, a[i]) - b;
      sizer = max(sizer, cache[i]);
      b[cache[i]] = a[i];
   }
}

void Xuat() {
   cout << sizer << '\n';

   vector<int> ans;

   for(int i = n; i >= 1; i--) {
      if(cache[i] == sizer) {
         ans.push_back(a[i]);
         sizer--;
      }
   }

   for(int i = ans.size() - 1; i >= 0; i--)
      cout << ans[i] << ' ';
}

int main() {
#ifdef LOCAL
   freopen("in.txt", "r", stdin);
#else
   freopen("LIS.inp", "r", stdin);
   freopen("LIS.out", "w", stdout);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0); cout.tie(0);

   cin >> n;
   for (int i = 1; i <= n; i++)
      cin >> a[i];

   DP();
   Xuat();

   return 0;
}