Cod sursa(job #320242)

Utilizator Addy.Adrian Draghici Addy. Data 4 iunie 2009 07:42:53
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#define DIM 100001 

int v[DIM],L[DIM],T[DIM];
int n,i,j,k,t,max,poz;

int main() {
	
	FILE *f = fopen("subsir.in","r");
	FILE *g = fopen("subsir.out","w");
	
	fscanf(f,"%d",&n);
	
	for (i=1; i<=n; i++)
		fscanf(f,"%d",&v[i]);
	
	L[1] = 1;
	
	for (i=2; i<=n; i++) {
		max = 0;
		poz = i;
		for (j=1; j<i; j++)
			if (v[j]<=v[i])
				if (L[j]>max) {
					max = L[j];
					poz = j;
				}
		L[i] = L[poz] + 1;
		T[i] = poz;
	}
	
	max = 0;
	
	for (i=1; i<=n; i++)
		if (L[i] > max) {
			max = L[i];
			poz = i;
		}
	
	t = poz;
	
	while (t) {
		L[++k] = v[t];
		t = T[t];
	}		
		
	fprintf(g,"%d\n",max);
	
	for (i=k; i>=1; i--)
		fprintf(g,"%d ",L[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}