Cod sursa(job #272785)

Utilizator RegeleUmbrelorPopescu Mihai RegeleUmbrelor Data 7 martie 2009 19:53:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
 #include <stdio.h>  
 #define N 101000 
int v[N],lung[N],n,p[N],max,sol[N],k;  
 void Remake()  
 {  
     int q=max;  
     sol[++k]=v[q];  
     while (q>=1)  
     {  
         int j=q-1;  
         while (j && (lung[j]!=lung[q]-1 || v[j]>=v[q]))  
             j--;  
         if(j)  
             sol[++k]=v[j];  
         q=j;  
     }  
     for (int i=k; i>=1; i--)  
         printf("%d ",sol[i]);  
 }  
 void Solve()  
 {  
     scanf("%d",&n);  
     for (int i=1; i<=n; i++)  
         scanf("%d",&v[i]);  
     lung[1]=1;  
     for (int i=2; i<=n; i++)  
     {  
         max=0;  
         for (int j=1; j<i; j++)  
             if (v[j]<v[i] && lung[j]>max)  
                 max=lung[j];  
         lung[i]=1+max;  
     }  
     max=1;  
     for (int i=1; i<=n; i++)  
         if (lung[i]>lung[max])  
             max=i;  
     printf("%d\n",lung[max]);  
     Remake();  
   
 }  
int main()  
 {  
     freopen("scmax.in","r",stdin);  
     freopen("scmax.out","w",stdout);  
     Solve();  
	 return 0;
 }