Cod sursa(job #497471)

Utilizator Ionut_ROStoica Ionut Ionut_RO Data 2 noiembrie 2010 16:53:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <memory.h>
using namespace std;

const int MAX_N = 10005;

int a[MAX_N], c[MAX_N], b[MAX_N];

void afisare (int a[], int k, int b[], int x[])
{
	if (x[k])
	{
		afisare (a, b[k], b, x);
		cout<<x[k]<<" ";
	}
}

int main ()
{
	freopen("scmax.in", "r", stdin);
	int i,j,n;
	memset(a, 0, sizeof a);
	memset(c, 0, sizeof c);
	
	cin>>n;
	for (i=1; i<=n; i++)
		cin>>a[i];
	
	for (i=1; i<=n; i++) {
		c[i]=1;
		for(j=i-1; j>=1; j--)
			if (a[j] < a[i] && c[i]<c[j]+1)
			{
					c[i]=c[j]+1;
					b[i]=j;
			}
			
	}
	
			
	freopen("scmax.out", "w", stdout);
	int max=0,k;
	for (i=n; i>=1; i--)
		if(c[i]>max)
		{
			max=c[i];
			k=i;
		}
	cout<<max<<endl;
	afisare (c, k, b, a);
		
			
	
	return 0;
}