Cod sursa(job #694269)

Utilizator lunat1cHobinca Bogdan lunat1c Data 27 februarie 2012 19:35:42
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>

using namespace std;

int n, a[100001], i, j, v[100001];

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

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

void dinamica()
{
	for(i=n; i>=1; i--)
	{
		int max=0;
		for(j=i+1; j<=n; j++)
			if(max<v[j] && a[i]<a[j])
				max=v[j];
		v[i]=max+1;
	}
	int max=0;
	for(i=1; i<=n; i++)
		if(max<v[i])
			max=v[i], j=i;
	out<<max<<'\n'<<a[j]<<' ';
	for(i=j+1; i<=n; i++)
		if(max==v[i]+1 && a[j]<a[i])
		{
			out<<a[i]<<' ';
			j=i;
			max=v[i];
		}

}

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