Cod sursa(job #175611)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 10 aprilie 2008 10:04:29
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 1.21 kb
/*      O(N^2)      */
#include <stdio.h>
#include <string.h>
#define N 100001
int n,v[N],lung[N],pred[N];
void scan(){
     int i,x,k=0,nr=0;
     char s[3000000];
     freopen("scmax.in","r",stdin);
     freopen("scmax.out","w",stdout);
     scanf("%d\n",&n);
     //for (i=1;i<=n;++i)
         //scanf("%d",&v[i]);
     gets(s);
     x=strlen(s);
     for (i=0;i<x;++i)
         if (s[i]==' '){
            ++k;
            v[k]=nr;
            nr=0;
         }
         else{
              nr=nr*10+(s[i]-'0');
         }
     ++k;
     v[k]=nr;
}
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();
    return 0;
}