Cod sursa(job #632870)

Utilizator roots4Irimia Alexandru Gabriel roots4 Data 12 noiembrie 2011 14:42:22
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#include <stdio.h>
int i , j , k , n , max=-10,maxi; 
int L[100009],Z[100009],V[100009];
int main(){
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	L[1]=1;Z[1]=1;
	scanf("%d",&V[1]);
	for(i=2;i<=n;i++){
		scanf("%d",&V[i]);
		
		for(j=1;j<=(i-1);j++){
			if(V[j]<V[i]){
				if((L[j]+1)>=L[i]){
					L[i]=L[j]+1;
					Z[i]=j;
				}
			}
		}
		if(L[i]==0)
			L[i]=1;
		if(L[i]>max){
			max=L[i];
			maxi=i;
		}
	}
	printf("%d\n",max);k=1;
	for(j=maxi;k<=max;j=Z[j],k++){
		L[k]=V[j];
	}
	for(i=max;i>=1;i--)
		printf("%d ",L[i]);
	
	return 0;
}