BOJ 14003 가장 긴 증가하는 부분 수열 5

1 개요

BOJ 14003 가장 긴 증가하는 부분 수열 5

• 백준 온라인 저지 14003번 문제
• BOJ 34단계

2 같이 보기

• BOJ 11053 가장 긴 증가하는 부분 수열
• BOJ 11054 가장 긴 바이토닉 부분 수열
• BOJ 11055 가장 큰 증가하는 부분 수열
• BOJ 11722 가장 긴 감소하는 부분 수열
• BOJ 12015 가장 긴 증가하는 부분 수열 2
• BOJ 12738 가장 긴 증가하는 부분 수열 3
• BOJ 14002 가장 긴 증가하는 부분 수열 4

3 C++

#include <bits/stdc++.h>
using namespace std;

int N;
int A[1000001];
int B[1000001];
vector<int> v;

void solve() {
    for (int i = 1; i <= N; i++) {
        if (v.size() == 0 || v[v.size() - 1] < A[i]) {
            v.push_back(A[i]);
            B[i] = v.size() - 1;
            continue;
        }
        int left = 0;
        int right = v.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (v[mid] >= A[i]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        v[left] = A[i];
        B[i] = left;
    }
    cout << v.size() << endl;
    int idx = v.size() - 1;
    stack<int> s;
    for (int i = N; i > 0; i--) {
        if (B[i] == idx) {
            idx--;
            s.push(A[i]);
        }
    }
	while(!s.empty()) {
	    cout << s.top() << ' ';
	    s.pop();
	}
}

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