Cod sursa(job #524523)

Utilizator valizZbant Valentin valiz Data 22 ianuarie 2011 10:16:01
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <cstdio>
using namespace std;
int im;
int lung[100001];
int urm[100001];
int idxPos;
int idxPos2;
int v[100001];
int nNo;

int main()
{
	int max;
	FILE* f=fopen("scmax.in","r");
	FILE* g=fopen("scmax.out","w");
	
	fscanf(f,"%d",&nNo);
	
	for (idxPos=1;idxPos<=nNo;idxPos++)
	{
		fscanf(f,"%d",&v[idxPos]);
	}
	
	lung[nNo] = 1;
	urm[nNo] = 0;
	
	for (idxPos = nNo - 1; idxPos >= 1; idxPos--)
	{
		max=0;
		im=0;
		
		for (idxPos2=idxPos+1;idxPos2<=nNo;idxPos2++)
		{
			if(v[idxPos] < v[idxPos2] && max < lung[idxPos2])
			{
				max = lung[idxPos2];
				im = idxPos2;
			}
		}
		
		lung[idxPos] = max+1;
		urm[idxPos] = im;
	}
	
	max = lung[1];
	im = 1;
	
	for (idxPos = 2;idxPos <= nNo; idxPos++)
	{
		if(max < lung[idxPos])
		{
			max = lung[idxPos];
			im = idxPos;
		}
	}
	
	fprintf(g,"%d\n",max);
	do
	{
		fprintf(g,"%d ",v[im]);
		im = urm[im];
	}
	while (im!=0);
	
	fclose(g);
	return 0;
}