Cod sursa(job #279951)

Utilizator robertzelXXX XXX robertzel Data 13 martie 2009 09:27:36
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#define NMAX 100000

typedef int sir[NMAX];
int n, i, j, max,x;
sir m, k;
FILE *in, *out;

void citeste ()
{
	in = fopen("scmax.in", "r");

	fscanf(in, "%d", &n);

	for (i=0; i<n; i++)
	{
		fscanf(in,"%d", &m[i]);
	}

	fclose(in);
}

void calculeaza ()
{
	k[n-1] = 1;

	//parcurge sirul incepand de la capat
	for (i=n-2; i>=0; i--)
	{
		//cauta un numar mai mare ca cel actual (cel din m[i])
		for (j=i+1; j<n; j++)
		{
			if ((m[j] > m[i]) && (k[i] < k[j]))
			{
				k[i] = k[j];
			}
		}

		k[i]++;

		if (k[i] > max) max = k[i];

		//verifica daca a gasit un numar mai mare
		if (k[i] == 0)
		{
			k[i] = 1;
		}
	}
}

void sirul ()
{
	out = fopen("scmax.out", "w");

	fprintf(out, "%d \n", max);

	max++;

	for (i=0; i<n; i++)
	{
		if ((k[i] < max) && ((k[i]!=1) || (i==n-1)))
		{
			fprintf(out, "%d ", m[i]);
			max--;
		}
	}

	fclose(out);
}

int main ()
{
	citeste();
	calculeaza();
	sirul();

	return 0;
}