Cod sursa(job #534675)

Utilizator Rares95Rares Arnautu Rares95 Data 15 februarie 2011 23:04:13
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <stdio.h>
#define MAX 100001

int a[MAX], v[MAX], t[MAX], n, i, j, max1, sol, p;

void read()
  {	freopen ("scmax.in","r", stdin);
		freopen ("scmax.out","w", stdout);
    scanf ("%d",&n);
    for (i = 1; i <= n; ++i) scanf ("%d", &a[i]);
  }
	
void solve()
{	v[n] = 1; t[n] = -1;
	max1 = 1; p = n;
	for(i = n - 1; i >= 1; --i)
		{	v[i] = 1; t[i] = -1;
			for (j = i + 1 ; j <=n; ++j)
			if (a[i] < a[j] && v[i] < v[j] + 1)
			{	v[i] = v[j]+1; t[i] = j;
				if (v[i] > max1) {max1 = v[i]; p=i;}
			}
    }
	i = p;
}

void write()
{	printf ("%d\n", max1);
	while (i != -1) {printf ("%d ",a[i]); i = t[i];}
	printf ("\n");
}
int main()
{	read();
	solve();
	write();
	return 0;
}