Cod sursa(job #204510)

Utilizator AdrianSoucupAdrian Soucup AdrianSoucup Data 24 august 2008 18:49:08
Problema Subsir 2 Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <stdio.h>

int main ()
{
	int a[5000], poz[5000], l[5000], i, j, pozmax=0, max, n;
	FILE *in, *out;
	in=fopen("subsir2.in", "r");
	out=fopen("subsir2.out", "w");

	fscanf(in, "%ld", &n);
	l[n-1]=1;
	poz[n-1]=-1;


	for(i=0; i<n; i++)
		fscanf(in, "%ld", &(a[i]));

	for(i=n-1; i>=0; i--)
		for(poz[i]=-1, l[i]=1, j=i+1; j<n; j++)
			if(a[i]<a[j]&&l[i]<l[j]+1)
			{
				l[i]=l[j]+1;
				poz[i]=j;
			}


	max=l[0];
	for(i=1; i<n; i++)
		if(l[i]>max)
			l[i]=max,
			pozmax=i;

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

	for(i=pozmax; i!=-1; i=poz[i])
		fprintf(out, "%ld ", i+1);
	fprintf(out, "\n");

	return 0;
}