Cod sursa(job #422191)

Utilizator zloteanu.adrianzloteanu adrian nichita zloteanu.adrian Data 22 martie 2010 12:12:44
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <stdio.h>
int n,max,k,x,a[100003],b[100003],c[100003],d[100003];//0
void afis(int i)
{if(c[i] > 0)
  afis(c[i]);
printf("%d ",a[i]);}
int caut(int x)
{int p, u, m;
p=0;
u=x;
m=(p+u)/2;
while(p<=u)
   {if(a[d[m]]<x&&a[d[m+1]] >= x)
     return m;
    else
     if(a[d[m+1]]<x)
      {p=m+1;
      m=(p+u)/2;}
     else
      {u=m-1;
      m=(p + u)/2;}}
   return x;}
int main()
{freopen("scmax.in","r",stdin);
freopen("scmax.out","w",stdout);
int i,j,poz;
x=1;
scanf("%d",&n);
for(i=1;i<=n;i++)
  scanf("%d", a + i);
b[1]=d[1] = 1;
d[0]=0;
for(i=2;i<=n;i++)
   {poz=caut(a[i]);
   c[i]=d[poz];
   b[i]=poz+1;
   d[poz+1]=i;
   if(x<poz+1)
    x=poz+1;}
   max=0;
   poz=0;
   for(i=1;i<=n;i++)
       if(max<b[i])
	{max=b[i];
	poz=i;}
   printf("%d\n",max);
   afis(poz);
   return 0;}