[C++][백준 12738] 가장 긴 증가하는 부분 수열 3

[문제]

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

12738번: 가장 긴 증가하는 부분 수열 3

[문제 풀이]

가장 긴 증가하는 부분 수열2 와 동일하게 생각하면 된다.

 

[코드]

#include<iostream>
#include<vector>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int main(){
    int n;
    cin>>n;
    vector<int> sequence;
    for(int i = 0;i<n;i++){
        int temp;
        cin>>temp;
        if(sequence.size() == 0 or sequence.back()<temp){
            sequence.push_back(temp);
        }
        else{
            *lower_bound(sequence.begin(),sequence.end(),temp) = temp;
        }
    }
    cout<<sequence.size()<<endl;
    return 0;
}