Cod sursa(job #331002)

Utilizator Addy.Adrian Draghici Addy. Data 12 iulie 2009 12:06:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <stdio.h>
#define DIM 100001

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

void search(int i) {
	best = 0;
	poz = 0;
	for (j=1; j<i; j++)
		if (v[j]<v[i])
			if (L[j] > best) {
				best = L[j];
				poz = j;
			}
}

void update(int i) {
	L[i] = L[poz] + 1;
	T[i] = poz;
}

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