Cod sursa(job #316613)

Utilizator pedobearBacauanu Vlad pedobear Data 20 mai 2009 14:14:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>

int d[100010],v[100010],a[100010];
int i,n,max,poz,maxf,pozf,j;

void recon (int lng, int start)
{
     if (lng==1) printf ("%d ",v[start]);
     else{
          recon (--lng, a[start]);
          printf ("%d ",v[start]);
          }
}

int main ()
{
    freopen ("scmax.in","r",stdin);
    freopen ("scmax.out","w",stdout);
    
    scanf ("%d",&n);
    for (i=1;i<=n;i++) scanf ("%d ",&v[i]);
    
    d[1]=1;
    
    for (i=2;i<=n;i++){
        max = 0, poz = 0;
        for (j=1;j<i;j++) 
            if (v[j]<v[i] && d[j]>max){
               max = d[j];
               poz = j;
               }
        d[i] = max + 1;
        a[i] = poz;
        if (d[i] > maxf) {
                 maxf = d[i];
                 pozf = i;
                 }
        }
        
    printf ("%d\n",maxf);
    recon(maxf,pozf);
    
    return 0;
}