Cod sursa(job #1185720)

Utilizator preda_alexandruPreda Alexandru preda_alexandru Data 16 mai 2014 15:42:07
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>

#define MAXN 100005

int n;
int a[MAXN];

// d[i] - cel mai lung subsir din primele i elemente
int best[MAXN];
int pre[MAXN];

void get_max(int n, int* max, int* p)
{
	*max = 0;
	*p = 0;

	for (int i = 1; i < n; i++) {
		if (a[i] < a[n] && best[i] > *max) {
			*max = best[i];
			*p = i;
		}
	}
}

void solve()
{
	int max, p;

	for (int i = 1; i <= n; i++) {
		get_max(i, &max, &p);

		best[i] = 1 + max;
		pre[i] = p;
	}
}

void print_helper(int p)
{
	if (p == 0)
		return;

	print_helper(pre[p]);
	
	printf("%d ", a[p]);
}

void print()
{
	int max = 0;
	int p = 0;

	for (int i = 1; i <= n; i++) {
		if (best[i] > max) {
			max = best[i];
			p = i;
		}
	}

	printf("%d\n", max);
	print_helper(p);
}



int main()
{
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

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

	solve();
	print();

	return 0;
}