Cod sursa(job #729373)

Utilizator raluca_vacaruVacaru Raluca-Ioana raluca_vacaru Data 29 martie 2012 15:36:02
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#define NMAX 100001

using namespace std;

int n, a[NMAX], d[NMAX];

void read() {
	int i;
	scanf("%d", &n);
	for (i=1; i<=n; ++i)
		scanf("%d", &a[i]);
}

int maxim(int y, int j) {
	int x = 0;
	for (int i=y; i<=j; ++i)
		if (a[i]>a[y-1] && d[i]>x)
			x = d[i];
	return x;
}

void solve() {
	int i;
	d[n] = 1;
	for (i=n; i>=1; --i)
		d[i] = maxim(i+1, n) + 1;
}

void afis() {
	int maxi = 0, i;
	for (i=1; i<=n; ++i)
		if (d[i]>maxi) maxi = d[i];
	printf("%d\n", maxi);
	for (i=1; i<=n; ++i)
		if (d[i] == maxi) {
			printf ("%d ", a[i]);
			--maxi;
		}
}

int main () {
	freopen("scmax.in","r",stdin);
	read();
	fclose(stdin);
	solve();
	freopen("scmax.out","w",stdout);
	afis();
	fclose(stdout);
	return 0;
}