Cod sursa(job #1504075)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 17 octombrie 2015 12:01:39
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>

struct{
    int len,prec;
}sol[100001];

int v[100001];

int vt[100001];

int main(){
    int n,i,max;
    int j,poz,x;

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

    scanf("%d",&n);

    for(i=0;i<n;i++){
        scanf("%d",&v[i]);
        sol[i].len=1;
        sol[i].prec=-1;
    }

    for(i=1;i<n;i++){
        max=0;
        poz=-1;
        for(j=0;j<i;j++){
            if(v[j]<v[i] && sol[j].len>max){
                max=sol[j].len;
                poz=j;
            }
        }
        sol[i].len=max+1;
        sol[i].prec=poz;
    }

    max=0;
    for(i=0;i<n;i++){
        if(max<sol[i].len){
            max=sol[i].len;
            j=i;
        }
    }
    printf("%d\n",sol[j].len);

    x=0;
    while(sol[j].prec!=-1){
        vt[x++]=v[j];
        j=sol[j].prec;
    }
    vt[x]=v[j];

    for(i=x;i>=0;i--){
        printf("%d ",vt[i]);
    }

    return 0;
}