# Cod sursa(job #251634)

Utilizator Data 2 februarie 2009 23:49:21 Subsir crescator maximal 100 cpp done Arhiva educationala 2.09 kb
``````#include <stdio.h>
#include <algorithm>

using namespace std;

#define Nsol 100100

int a[Nsol], best[Nsol], norm[Nsol], n, sol, t[Nsol], rec[Nsol];

/*
void qsort(int st,int dr)
{
int i=st,j=dr,sch=norm[(st+dr)/2],tmp;
do{
while (norm[i] < sch) ++i;
while (norm[j] > sch) --j;
if (i<=j)
{
tmp = norm[i];
norm[i] = norm[j];
norm[j] = tmp;
++i; --j;
}
} while (i<=j);
if (st < j) qsort(st,j);
if (i < dr) qsort(i,dr);
}
*/
int aib[Nsol];

void up(int x,int nr)
{
for (;x<=n;x+=x&(x-1)^x)
if (best[aib[x]] < best[nr])
aib[x] = nr;
}

int q(int x)
{
int ret=0;
for (;x;x-=x&(x-1)^x)
if (best[aib[x]] > best[ret])
ret = aib[x];
return ret;
}

#define Dim 10000
#define buff fread(buf,Dim,1,stdin), poz = 0

char buf[Dim];
int poz;

int cit()
{
int ret = 0;
while (buf[poz] < 48) if (++poz == Dim) buff;
while (buf[poz] > 47)
{
ret = ret*10 + buf[poz] - 48;
if (++poz == Dim) buff;
}
return ret;
}

int main()
{
freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);

buff;

//scanf("%d", &n);
n = cit();

for (int i=1;i<=n;++i)
{
//scanf("%d", a+i);
a[i] = cit();
norm[i] = a[i];
}

sort(norm+1,norm+n+1);

for (int i=1;i<=n;++i)
{
//indice
int ind=0;
for (int x=1<<17;x;x/=2) if (ind+x <= n)
if (norm[ind+x] <= a[i]) ind+=x;
//aflu best
int before = q(ind-1);
t[i] = before;
best[i] = best[before]+1;
//update
up(ind,i);
if (best[i] > best[sol]) sol = i;
}

printf("%d\n", best[sol]);

int tmp = sol;

while (tmp > 0)
{
rec[best[tmp]] = tmp;
tmp = t[tmp];
}

for (int i=1;i<=best[sol];++i)
printf("%d ", a[rec[i]]);
printf("\n");

return 0;
}

``````