Cod sursa(job #661913)

Utilizator cristian9Cristian Zloteanu cristian9 Data 15 ianuarie 2012 15:08:27
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
int d[100001], maxt, v[100001], sol[100001];
int main(){
    freopen ("scmax.in", "r", stdin);
    freopen ("scmax.out", "w", stdout);

    int i, n, j, max, pre;

    scanf("%d ", &n);
    for(i=1; i<=n; i++)
        scanf("%d ", &v[i]);
    d[1]=1;
    for(i=2; i<=n; i++){
        max=0;
        for(j=i-1; j>=1; j--)
            if(v[j]<v[i])
                if(max<d[j])
                    max=d[j];
        d[i]=max+1;
        if(d[i]>maxt)
            maxt=d[i];
            pre=v[i];
    }

    printf("%d\n", maxt);
    pre++;j=1;
    for(i=n; i>=1; i--)
        if(d[i]==maxt)
            if(v[i]<pre){
                //printf("%d ", v[i]);
                sol[j++]=v[i];
                pre=v[i];
                maxt--;
            }
    for(i=j-1; i>=1; i--)
        printf("%d ", sol[i]);
    return 0;
}