Cod sursa(job #1089206)

Utilizator adrianvVasiu Adrian-Daniel adrianv Data 21 ianuarie 2014 16:20:52
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
using namespace std;
FILE *in, *out;
int n,v[1000000],v2[1000000],best,vect[100000];
int main()
{
	in = fopen("scmax.in", "rt");
	out = fopen("scmax.out", "wt");

	fscanf(in,"%d",&n);
	for(int i=1;i<=n;i++)
		fscanf(in,"%d",&v[i]);
	
	v2[1]=1;
	best=1;
	for(int i=2;i<=n;i++)
	{
		best=0;
		for(int j=i-1;j>=1;j--)
		{
			if(v[i]>v[j] && v2[j]>best)
			{
				best=v2[j];
			}
		}
		v2[i]=best+1;
	}
	int a=1;
	for(int i=1;i<=n;i++)
	{
		if(v2[i]>a)
			a=v2[i];
	}
	fprintf(out,"%d \n",a);
	int b=a;
	
	int i=n;
	int j=1;
	while(i)
	{
		if(v2[i]==a)
		{
			vect[j++]=v[i];
			a--;
			
		}
		i--;
	}
	for(i=b;i>=1;i--)
		fprintf(out,"%d ",vect[i]);

	fclose(in);
	fclose(out);
	return 0;
}