Pagini recente » Cod sursa (job #2502134) | Cod sursa (job #1696753) | Cod sursa (job #2460969) | Cod sursa (job #1601981) | Cod sursa (job #3200213)
#include <fstream>
using namespace std;
const int Vmax = 100001;
int a[Vmax], minVal[Vmax], pre[Vmax];
int n, lMax;
void inbetween(int st, int dr, int x){
if(st==dr){
if(x <= minVal[st]){
pre[x] = minVal[st-1];
minVal[st] = x;
}
else{
pre[x] = minVal[st];
minVal[st+1] = x;
}
return;
}
int mij = (st+dr)/2;
if(x <= minVal[mij])
return inbetween(st, mij, x);
else
return inbetween(mij+1, dr, x);
}
int main(){
ifstream fin("scmax.in");
ofstream fout("scmax.out");
fin>>n;
for(int i=1;i<=n;i++)
fin>>a[i];
for(int i=1;i<=n;i++){
if(minVal[lMax] < a[i]){
pre[a[i]] = minVal[lMax];
lMax++;
minVal[lMax] = a[i];
}
else
inbetween(1, lMax, a[i]);
}
fout<<lMax<<'\n';
int sol[lMax];
int j=minVal[lMax];
for(int i=lMax;i>=1;i--){
int precedentul = j;
sol[i] = precedentul;
j = pre[precedentul];
}
for(int i=1;i<=lMax;i++)
fout<<sol[i]<<" ";
}