백준 알고리즘 3745번 : 오름세

링크

https://www.acmicpc.net/problem/3745

sol1) LIS + lower_bound

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

int32_t main() {
  fastio;
  int n;
  while(cin >> n){
    vector<int> table(n),ans;
    for(int i = 0; i < n; i++) cin >> table[i];
    for(int i = 0; i < n; i++){
      if(ans.empty() || ans.back() < table[i]) ans.push_back(table[i]);
      else *lower_bound(ans.begin(), ans.end(), table[i]) = table[i];
    }
    cout << ans.size() << "\n";
  }
}