[14002] 가장 긴 증가하는 부분수열4

// 14002 가장 긴 증가하는 부분 수열4 

#include<iostream>
#include<cstdio>
#include<string.h>
#include<vector>
#define MAX 1000
using namespace std;

int arr[MAX]; // 숫자  
int L[MAX], P[MAX];
int len, N;

void backtrace(int idx, int num){
	if(idx==0) return ;
	if(P[idx] == num){
		backtrace(idx-1, num-1);
		printf("%d ", arr[idx]);
	}else{
		backtrace(idx-1, num);
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	// 초기화  
	memset(arr, 0, MAX);
	memset(L, 0, MAX);
	memset(P, 0, MAX);

    scanf("%d", &N); // 숫자의 갯수  

	// 수 입력  
    for(int i=1; i<=N; i++){
   		scanf("%d", &arr[i]); // 1 ~ 1000   
   		auto pos = lower_bound(L+1, L+len+1, arr[i]);
   		*pos = arr[i];
   		P[i] = distance(L, pos);
   		if(pos == L+len+1) len++;
	}
	printf("%d\n", len);
	backtrace(N, len);
	
	return 0;
}