Cod sursa(job #502366)

Utilizator costin22Muraru Costin costin22 Data 19 noiembrie 2010 08:35:24
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h> 
const int maxn=100001; 
int i,N,max,pmax,a[maxn],Smax[maxn],pre[maxn],next[maxn]; 
void citire() 
{ 
scanf("%d",&N); 
for(i=1;i<=N;i++) scanf("%d",&a[i]); 
} 
void pd() 
{ 
int j; 
Smax[0]=0; pre[0]=-1; max=-1; 
for(i=1;i<=N;i++) 
    
{ 
        
for(j=0;j<i;j++) 
    
{ 
 
 if(a[j]<a[i] && Smax[j]+1>Smax[i]) 
{ 
    
Smax[i]=Smax[j]+1; 
    
pre[i]=j; 
    
if(Smax[i]>max) 
    
{ 
        
max=Smax[i]; pmax=i;} 
    
} 
} 
} 
} 
void constr() 
 
 
{ 
 
 
int nr; 
 
 
next[0]=nr=max; 
 
 
for(i=pmax;pre[i]!=-1;i=pre[i]) 
 
 
{ 
 
 
next[nr--]=i; 
 
 
} 
 
 
} 
 
 
  
 
 
 
int main() 
 
 
{ 
 
 
freopen("scmax.in","r",stdin); 
 
 
freopen("scmax.out","w",stdout); 
 
 
citire(); 
 
 
pd(); 
 
 
constr(); 
 
 
printf("%d\n",max); 
 
 
for(i=1;i<=next[0];i++) printf("%d ",a[next[i]]);  
 
}