# Cod sursa(job #251626)

Utilizator Data 2 februarie 2009 23:38:53 Subsir crescator maximal 70 cpp done Arhiva educationala 1.65 kb
``````#include <stdio.h>

#define Nmax 100100

int a[Nmax], best[Nmax], norm[Nmax], n, max, t[Nmax], rec[Nmax];

void sort(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) sort(st,j);
if (i < dr) sort(i,dr);
}

int aib[Nmax];

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;
}

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

scanf("%d", &n);

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

sort(1,n);

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[max]) max = i;
}

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

int tmp = max;

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

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

return 0;
}

``````