Cod sursa(job #752377)

Utilizator Victor10Oltean Victor Victor10 Data 28 mai 2012 15:22:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <cstdio>

int v [100005], best [100005], pre [100005], retine [100005];

int main () {
	
	freopen ("scmax.in", "r", stdin);
	freopen ("scmax.out", "w", stdout);
	
	int n, i, j, pozmaxx;
	
	scanf ("%d", &n);
	
	for (i = 1; i <= n; ++ i)
		scanf ("%d", &v [i]);
	
	best [0] = 0;
	for (i = 1; i <= n; ++ i) {
		pozmaxx = 0;
		for (j = i - 1; j >= 1; -- j)
			if (v [j] < v [i] && best [j] > best [pozmaxx]) {
				pozmaxx = j;
			}
		best [i] = best [pozmaxx] + 1;
		pre [i] = pozmaxx;
	}
	
	pozmaxx = 0;
	for (i = 1; i <= n; ++ i)
		if (best [i] > best [pozmaxx])
			pozmaxx = i;
	
	printf ("%d\n", best [pozmaxx]);
	for (; pozmaxx; pozmaxx = pre [pozmaxx])
		retine [++ retine [0]] = pozmaxx;
	
	for (i = retine [0]; i >= 1; -- i) 
		printf ("%d ", v [retine [i]]);
	
	printf ("\n");
}