Cod sursa(job #320745)

Utilizator Addy.Adrian Draghici Addy. Data 5 iunie 2009 18:14:36
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <stdio.h>
#define DIM 100001

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

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]);
	
	L[1] = 1;
	
	for (i=2; i<=n; i++) {
		search(i);
		update(i);
	}
	
	best = 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>=1; i--)
		fprintf(g,"%d ",L[i]);
	
	fclose(f);
	fclose(g);
	
	return 0;
}