Cod sursa(job #413681)

Utilizator encyEnciu Bogdan ency Data 8 martie 2010 22:08:32
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <stdlib.h>
void dinamic(long *a,long *best,long i,long n){
     if (i==0) best[i]=1;
     if (i==n) return;
     int d=best[0];
        long j;
        for(j=0;j<i;j++)
            if (a[i]>a[j])
            if (best[j]>d)
                d=best[j];
        for( j=0;j<i;j++)
            if (a[i]>a[j])
                        best[i]=1+d;
        dinamic(a,best,++i,n);
    }
long rec(long *a,long *best,long *s,long n){
        long max=best[n-1];
        long k=0;
        for(long i = n-1;i>=0;i--)
            if(best[i]>max)
                    max=best[i];
        long j=n-1;
        while(max>=1){
            if (best[j]==max) {
                s[k++]=a[j];
                --max;
            }
        j--;
        }
        return k;
        }
int main() {
         long a[100000],best[100000];
         long n;
         
        freopen("scmax.in", "r", stdin); 
        freopen("scmax.out", "w", stdout);  
        scanf("%l", &n); 
        for (long i=0;i<n;i++)     
        scanf("%d", &a[i]); 
        for (long i=0;i<n;i++) 
        best[i]=1;
        dinamic(a,best,0,n);
        long k;
        long s[n];
        k=rec(a,best,s,n);
        printf("%l \n",k);
        for(long i=k-1;i>=0;i--)
        printf("%l ",s[i]);
        return 1;
        }