Cod sursa(job #413682)

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