[BOJ-12015]가장 긴 증가하는 부분 수열2

이것도 가장 긴 증가하는 부분 수열1 과 동일하게 풀면 된다.

그런데 N이 1,000 이 아니라 1,000,000 백만이기 때문에 4달전에 풀었던 코드로는 풀 수 없고, 

lower_bound 를 사용해서 풀어야 풀리는 문제이다.

소스는 동일하다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
 
typedef vector<int> VI;
 
int main(){
    int n;    
    scanf("%d", &n);
    VI num = VI(0);
    for(int i = 0 ; i < n ; i++){
        int input;
        scanf("%d", &input);
        num.push_back(input);
    } // input seq of num 
 
    VI seq = VI(0);
    seq.push_back(num[0]);
    for(int i = 1 ; i < n ; i++){
        int here = num[i];
        auto index = lower_bound(seq.begin(), seq.end(), here);
        
        if( index == seq.end() ) seq.push_back(here);
        else if( index < seq.end() )  *index = here;        
    }
 
    printf("%d", seq.size());
    
    return 0;
}