(C++) - 백준(BOJ) 12738번 : 가장 긴 증가하는 부분 수열 3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#define MIN -2000000000
using namespace std;
int n,cnt;
int a[1000001];
vector <int> ans ;
int main() {
    cin >> n;
    ans.push_back(MIN);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++)
    {
        int big = a[i];
        if (ans.back() < a[i])
        {
            ans.push_back(a[i]);
            cnt++;
        }
        //lower_bound : 3번째 인자보다 큰 것중 가장 작은 값의 인덱스의 주소를 반환해준다.
        else
        {
            auto it = lower_bound(ans.begin(), ans.end(), a[i]);
            *it = big;
        }
    }
    cout << cnt << '\n';
 
}