Cod sursa(job #738806)

Utilizator Nicusor002Telechi Nicolae Nicusor002 Data 21 aprilie 2012 16:49:22
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<stdio.h>
#define dim 100005
int n,v[dim],best[dim],urmator[dim];

int main(){
    int i,j,beg,max=0;
    freopen("scmax.in","r",stdin);
    freopen("scmax.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&v[i]);
    best[n]=1;
    for(i=n-1;i>=1;i--){
        for(j=i+1;j<=n;j++){
            if(v[i]<v[j] && best[j]+1>best[i]){
                best[i]=best[j]+1;
                urmator[i]=j;
                if(max<best[i]){
                    max=best[i];
                    beg=i;
                }
            }
        }
    }
    printf("%d\n",max);
    for(i=beg;i;i=urmator[i]) printf("%d ",v[i]);
    return 0;
}