Cod sursa(job #1007100)

Utilizator BLz0rDospra Cristian BLz0r Data 8 octombrie 2013 11:50:05
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
using namespace std;

FILE *f=fopen ("scmax.in","r");
FILE *g=fopen ("scmax.out","w");

int v[100005],D[100005];

void remake (int val,int poz,int vmax){
	if (val==0) return;
	for (int i=1;i<poz;++i){
		if (D[i]==val && v[i]<vmax){
			remake (val-1,i,v[i]);
			fprintf (g,"%d ",v[i]);
			return;
		}
	}
}

int main(){
	int n,max=-1,mx,poz,i,j;
	
	fscanf (f,"%d",&n);
	
	for (i=1;i<=n;++i) fscanf (f,"%d",&v[i]);
	
	for (i=1;i<=n;++i){
		D[i]=1; mx=0;
		for (j=1;j<i;++j){
			if (v[j]<v[i] && D[j]>mx) mx=D[j];
		}
		D[i]=mx+1;
		if (D[i]>max){ max=D[i]; poz=i;}
	}
	fprintf (g,"%d\n",max);
	remake(max-1,poz,v[poz]);
	fprintf (g,"%d",v[poz]);
	
	
	return 0;
}