Cod sursa(job #175605)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 10 aprilie 2008 09:58:22
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.88 kb
#include <stdio.h>
const int N = 100001;
int n,v[N],lung[N],pred[N];
void scan(){
     int i;
     freopen("scmax.in","r",stdin);
     freopen("scmax.out","w",stdout);
     scanf("%d",&n);
     for (i=1;i<=n;++i)
         scanf("%d",&v[i]);
}
void solve(){
     int i,j;
     lung[1]=1;pred[1]=-1;
     for (i=2;i<=n;++i){
         lung[i]=1;pred[i]=-1;
         for (j=1;j<i;++j)
             if (v[j]<v[i] && lung[j]>=lung[i]){
                lung[i]=lung[j]+1;
                pred[i]=j;
             }
     }
}
void subsir(int x){
     if (pred[x]>=0)
        subsir(pred[x]);
     printf("%d ",v[x]);
}
void print(){
     int i,max=0,nmax=0;
     for (i=1;i<=n;++i)
         if (lung[i]>max){
            max=lung[i];
            nmax=i;
         }
     printf("%d\n",max);
     subsir(nmax);
}
int main(){
    scan();
    solve();
    print();
}