#include<cstdio>
#include<cstring>
#include<cstdlib>
#define max 200000
template <class DataType>
class LIS{
public:
int size;
DataType X[max];
private:
int index[max];
int length[max];
DataType Lis[max];
int LisLength;
public:
LIS(){};
void Operation(){
int i,j;
int ptr,len;
index[0] = -1;
length[0] = 1;
for(i=1;i<size;i++){
len = 0;
ptr = -1;
for(j=0;j<i;j++)
if(X[j] < X[i] && length[j] > len){
len = length[j];
ptr = j;
}
length[i] = len + 1;
index[i] = ptr;
}
len = 0;
ptr = -1;
for(i=0;i<size;i++)
if(length[i] > len){
len = length[i];
ptr = i;
}
LisLength = len;
for(i=len-1;i>=0;i--){
Lis[i] = X[ptr];
ptr = index[ptr];
}
for(i=0;i<len;i++)
printf("%d ",Lis[i]);
};
};
int main(){
LIS<int> lis;
lis.size = 11;
lis.X[0] = 66;
lis.X[1] = 92;
lis.X[2] = 123;
lis.X[3] = 31;
lis.X[4] = 83;
lis.X[5] = 53;
lis.X[6] = 48;
lis.X[7] = 17;
lis.X[8] = 9;
lis.X[9] = 57;
lis.X[10] = 75;
lis.Operation();
return 0;
}
