12015 가장 긴 증가하는 부분 수열 2

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

lower_bound를 이용해서 O(nlogn)만에 LIS를 만들 수 있다. 직접 예제들을 만들어서 동작 과정을 살펴보면 이해가 쉽다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n,m;
    scanf("%d",&n);
    vector<int> l;
    l.push_back(-1);
    while(n--)
    {
        scanf("%d",&m);
        if(l.back()<m) l.push_back(m);
        else *lower_bound(l.begin(),l.end(),m)=m;
    }
    printf("%d\n",l.size()-1);
    return 0;
}