[백준] 민균이의 계략(11568)

문제 링크 : [백준] 민균이의 계략(11568)

문제 설명

대놓고 LIS 구현문제입니다.

입력

N(행렬의 길이, 1<=N<=2,000)
D_i(i번째 수열의 수, 1<= D₁ <= 100,000,000)

5
8 9 1 2 10

출력

가장 긴 수열의 길이

3

카테고리

#DP #LIS

시간 복잡도 상한

O(N²logN)

해결 방법

1. LIS를 구현합니다.

시간복잡도

O(NlogN)

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n,d;
vector<int>v;
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d",&d);
        if(v.empty()||v.back()<d)v.push_back(d);
        else v[lower_bound(v.begin(),v.end(),d)-v.begin()]=d;
    }
    printf("%d",v.size());
}