Cod sursa(job #907629)

Utilizator Mihnea35Gall Mihnea Mihnea35 Data 8 martie 2013 09:36:37
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>

using namespace std;

int n, x[100001], l[100001];

void citire () {
	int i;
	ifstream f("scmax.in");
	f >> n;
	for (i=1; i<=n; i++) f >> x[i];
	f.close();
}

int calcul (int i) {
	int j, max = 0;
	for (j=i+1; j<=n; j++)
		if (l[j] > max && x[i] <= x[j]) max = l[j];
	return max;
}

void dp () {
	int i;
	l[n] = 1;
	for (i=n-1; i>=1; i--)
		l[i] = 1 + calcul(i);
}

void afisare () {
	int i, j, max = 0, p, u = 0;
	for (i=1; i<=n; i++)
		if (l[i] > max) {max = l[i]; p = i;}
	ofstream g ("scmax.out");
	g << max << '\n';
	j = p;
	for (i=max; i>=1; i--)
		for ( ; j<=n; j++)
			if (l[j] == i && x[j] >= u) {g << x[j] << ' '; u = x[j]; break;}
			
	g.close();
}

int main () {
	citire();
	dp();
	afisare();
	return 0;
}