Cod sursa(job #627954)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 31 octombrie 2011 00:35:58
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<cstdio>
#include<vector>

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

int n;
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 i, j, maxim, poz;
	fscanf(in, "%d", &n);
	
	for (i = 0; i < n; i++) fscanf(in, "%lld", &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;
		prec[i] = poz;
	}
	
	fprintf(out, "%d\n", lis[n-1]);
	Afiseaza(n-1);
	return 0;
}