Cod sursa(job #1342807)

Utilizator anaid96Nasue Diana anaid96 Data 14 februarie 2015 15:51:00
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<stdio.h>

FILE *in, *out;

//definitions

//constants
const int sz = (int) 1e5+1;
const int oo = (1<<30)-1;

//variables
int numbers;
int a[sz];
int Lmax[sz];
int maxim;
int start;

//functions

int main(void)
{
	in = fopen("scmax.in", "rt");
	out = fopen("scmax.out", "wt");
	
	fscanf(in, "%d", &numbers);
	
	for(int i=1; i<=numbers; ++i)
		fscanf(in,"%d", &a[i]);
	
	Lmax[numbers] = 1;
	
	for(int i=numbers-1; i>=1; --i)
	{
		Lmax[i] = 1;
		for(int j=i+1; j<=numbers; ++j)
		{
			if(a[i] < a[j])
			{
				if(Lmax[i] < Lmax[j]+1)
				{
					Lmax[i] = Lmax[j] + 1;
					if(Lmax[i] > maxim)
					{
						maxim = Lmax[i];
						start = i;
					}		
				}					
			}
		}
	}
	
	fprintf(out,"%d\n", maxim);
	fprintf(out, "%d ", a[start]);
	maxim--;
	for(int i=start+1; i<=numbers; ++i)
		if(Lmax[i] == maxim)
		{
			fprintf(out, "%d ",a[i]);
			maxim--;
		}
	
	fclose(in);
	fclose(out);
	return 0;
}