# Cod sursa(job #251620)

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

#define Nmax 100100

int a[Nmax], best[Nmax], norm[Nmax], n, max, t[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;
}

void rec(int nr)
{
if (t[nr]) rec(t[nr]);
printf("%d ", a[nr]);
}

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]);

rec(max);

return 0;
}

``````