Cod sursa(job #559682)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 17 martie 2011 23:32:26
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream>
#define dim 100002

using namespace std;

ifstream f("scmax.in");
ofstream g("scmax.out");

int a[dim],n;
int lg[dim];

void citire()
{
	int i;
	f>>n;
	for(i = 1;i <= n; i++)
		f>>a[i];
}

void dinamic()
{
	int i,j,t;
	int maxim;
	lg[n]=1;
	for(i = n - 1;i >= 1; i--)
	{
		maxim = 0;
		for(j = i + 1;j <= n; j++)
			if(a[j] > a[i] && lg[j] > maxim )
				maxim = lg[j];
			lg[i] = maxim + 1;
	}
	maxim = 0;
	for(i = 1;i <= n; i++)
		if(maxim<lg[i])
		{
			maxim = lg[i];
			t = i;
		}
		
		g<<maxim<<"\n";
		g<<a[t]<<" ";
		for(i = t + 1;i <= n; i++)
			if(a[t] < a[i] && maxim - 1 == lg[i])
			{
				g<<a[i]<<" ";
				maxim--;
			}
			
	
}

int main()
{
	citire();
	dinamic();
	return 0;
}