Cod sursa(job #304775)

Utilizator utcistuBarcau Tomsa utcistu Data 15 aprilie 2009 12:21:39
Problema Subsir crescator maximal Scor 55
Compilator c Status done
Runda Arhiva educationala Marime 0.91 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 2000000001

void search(int *best,int x,int *dim)
{
    int cnt,step;
    for (step=1;step<*dim;step<<=1);
    for (cnt=0;step;step>>=1)
    {
        if (cnt+step<=*dim)
        if (best[cnt+step]<=x) cnt+=step;
    }
    if (best[cnt]!=x)
    {
        best[cnt+1]=x;
        if (cnt==*dim)
        (*dim)++;
    }
}

int main()
{
    int *v,*best,n,i,dim=0;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    v=(int *)malloc(sizeof(int)*(n+1));
    best=(int *)malloc(sizeof(int)*(n+1));
    for (i=1;i<=n;i++) best[i]=INF;
    best[0]=0;
    for (i=1;i<=n;i++) scanf("%d",v+i);
    best[1]=v[1];
    for (i=2;i<=n;i++)
    {
        search(best,v[i],&dim);
    }
    printf("%d\n",dim);
    for (i=1;i<=dim;i++) printf ("%d ",best[i]);
    fclose(stdout);
    return 0;
}