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

1 개요

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

• 백준 온라인 저지 12015번 문제
• BOJ 27단계

2 같이 보기

• BOJ 11053 가장 긴 증가하는 부분 수열

3 C++

#include <iostream>
using namespace std;

int N;
int A[1000001];

int B[1000001];
int pos;

int search(int x) {
    int start = 1;
    int end = pos;
    int mid;
    while(start < end) {
        mid = start + (end-start)/2;
        if(B[mid] >= x) {
            end = mid;
        } else {
            start = mid+1;
        }
    }
    return end;
}

int solve() {
    B[1] = A[1];
    pos = 1;
    for(int i=2; i<=N; i++) {
        if(A[i] > B[pos]) {
            pos++;
            B[pos] = A[i];
        } else {
            B[search(A[i])] = A[i]; 
        }
    }
    return pos;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> A[i];
    }
    cout << solve();
}