Cod sursa(job #1140759)

Utilizator 0x7c00Gabriel Ciubotaru 0x7c00 Data 12 martie 2014 11:21:34
Problema Subsir crescator maximal Scor 70
Compilator c Status done
Runda Arhiva educationala Marime 0.77 kb
#define _CRT_SECURE_NO_WARNINGS
#include <malloc.h>
#include <stdio.h>
#include <string.h>
#define NAME "scmax"
#define OPEN f = fopen(NAME".in","r");g = fopen(NAME".out","w");
FILE *f,*g;

int best[100000];
int v[100000];
int sol[100000];

int n,i,max,j,el;
int main()
{
	OPEN;
	fscanf(f,"%d",&n);
	for(i=0;i<n;i++)
		fscanf(f,"%d",&v[i]);
	for(i=0;i<n;i++)
	{
		max = 0;
		for(j=0;j<i;j++)
			if((v[j] < v[i]) && (best[j] > max))
				max = best[j];
		best[i] = max+1;
	}
	max = 0;
	for(i=0;i<n;i++)
		if(best[i] > max)
			max = best[i];
	fprintf(g,"%d\n",max);
	el = 2000000001;
	j=0;
	for(i=n-1;i>=0;i--)
	{
		if((max == best[i])&&(v[i] < el))
		{
			el = v[i];
			max --;
			sol[j++] = el;
		}
	}
	while(j--)
		fprintf(g,"%d ",sol[j]);
}