Cod sursa(job #496746)

Utilizator cristian9Cristian Zloteanu cristian9 Data 30 octombrie 2010 14:27:59
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include<stdio.h>

int v[100001], best[100001], maxt;

int main(){
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);

    int n, i, j;

    scanf("%d ", &n);
    best[n]=1;

    for(i=1; i<=n; i++)
        scanf("%d ", &v[i]);

    for(i=n; i>=1; i--){
        int max=0;
        for(j=i+1; j<=n; j++){
            if(v[i]<v[j])
                if(best[j]>=max)
                    max=best[j];
        }
        best[i]=max+1;
        if(best[i]>maxt)
            maxt=best[i];
    }

    printf("%d\n", maxt);
    for(i=1; maxt>0; i++)
        if(best[i]==maxt){
            printf("%d ", v[i]);
            maxt--;
        }

    return 0;
}