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

dp로 풀려고 했는데 시간복잡도가 제곱이라 안될거 같아서 이분 탐색을 써야겠다는 생각이 들었다.

수열을 앞에서부터 읽으면서 가장 긴 증가하는 부분 수열 lis라는 배열을 따로 만들어서 값을 채워간다.

수열의 값이 lis의 마지막 값, 즉 가장 큰 값보다 더 크면 lis의 크기를 늘리고 맨 뒤에 추가시켜준다.

lis의 마지막 값보다 크지 않을 때는 수열의 값이 lis 배열 내에서 어디 위치해야 하는지 이분탐색으로 찾아주고, 대체해준다.

예를 들어서 10 20 40 이 있는 경우에 15가 들어오면 15는 10과 20 사이인데 20을 대체해서 10 15 40으로 만들어준다.

#include<stdio.h>
int N,ans;
int lis[1000004];
int pos(int s, int e, int v)
{
    if(s==e) return s;
    int mid = (s+e)/2;
    if(lis[mid]<v){
        return pos(mid+1,e,v);
    }
    else{
        return pos(s,mid,v);
    }
}
int main()
{
    scanf("%d",&N);
    for(int i=1;i<=N;i++){
        int a;
        scanf("%d",&a);
        if(ans==0){
            ans=1;
            lis[ans]=a;
        }
        else{
            if(lis[ans]<a){
                ans++;
                lis[ans]=a;
            }
            else{
                int x = pos(1,ans,a);
                lis[x]=a;
            }
        }
    }
    printf("%d",ans);

}

이분탐색 구현은 그냥 하면 되고 전체 해결 코드이다.