Cod sursa(job #627957)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 31 octombrie 2011 00:54:57
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<cstdio>
#include<vector>

FILE *in = fopen ("scmax.in", "r"), *out = fopen ("scmax.out", "w");
using namespace std;

vector <int> sir(100001), prec(100001), lis(100001, 0);

void Afiseaza(int poz){
	if (prec[poz] == poz)	{ fprintf(out, "%d ", sir[poz]);	return;}
	Afiseaza(prec[poz]);
	fprintf(out, "%d ", sir[poz]);
}
	
int main(){
	int n, i, j, maxim, poz, M = 0, P;
	fscanf(in, "%d", &n);
	
	for (i = 0; i < n; i++) fscanf(in, "%d", &sir[i]);
	for (i = 0; i < n; i++){
		maxim = 0;
		poz = i;
		for (j = 0; j < i; j++)
			if (sir[j] < sir[i] && lis[j] > maxim){
				maxim = lis[j];
				poz = j;
			}
		lis[i] = maxim + 1;
		if (M < maxim + 1) {M = maxim + 1; P = i;}
		prec[i] = poz;
	}
		
	fprintf(out, "%d\n", lis[P]);
	Afiseaza(P);
	return 0;
}