백준 12738 가장 긴 증가하는 부분 수열 3

Longest Increasing Subsequence (가장 긴 증가하는 부분 수열) 문제

#include <iostream>
#include <vector>
#define BIG 1000007
using namespace std;

int N;
vector<int> arr;
vector<int> LIS;

void input(){
  cin >> N;
  arr.resize(N,0 );
  for(int i = 0; i < N; i++){
    cin >> arr[i];
  }
}

void binary_search(int num){
  int left = 0;
  int right = LIS.size();
  int tmp = BIG;
  int mid;
  while(left <= right){
    mid = (left + right)/2;
    int cur = LIS[mid];
    if(cur >= num){
      if(tmp > mid){
        tmp = mid;
      }
      right = mid - 1;
    }
    else{
      left = mid + 1;
    }
  }
  LIS[tmp] = num;
}

void find(){
  LIS.push_back(arr[0]);
  for(int i = 1; i < N; i++){
    if(LIS.back() < arr[i]){
      LIS.push_back(arr[i]);
    }
    else{
      binary_search(arr[i]);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  input();
  find();
  cout << LIS.size() << "\n";
  return 0;
}