Cod sursa(job #753359)

Utilizator Victor10Oltean Victor Victor10 Data 29 mai 2012 21:03:20
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <cstdio>

int a [100005], p [100005], best [100005], pre [100005], sol [100005];

void makesol (int pozmaxx) {
	for (; pozmaxx; pozmaxx = pre [pozmaxx])
		sol [++ sol [0]] = pozmaxx;
}

void writesol () {
	int i;
	for (i = sol [0]; i >= 1; -- i)
		printf ("%d ", a [sol [i]]);
	printf ("\n");
}

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