Cod sursa(job #1027923)

Utilizator vladrochianVlad Rochian vladrochian Data 13 noiembrie 2013 11:37:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.47 kb
#include <fstream>
using namespace std;
int n,i,j,a[100000],b[100000],s[100000],m;
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int main()
{
	fin>>n;
	for(i=0;i<n;i++)
		fin>>a[i];
	m=n-1;
	for(i=n-1;i>=0;i--)
	{
		b[i]=0;
		s[i]=-1;
		for(j=i+1;j<n;j++)
			if((b[j]>b[i])&&(a[i]<a[j]))
				b[i]=b[j],s[i]=j;
		b[i]++;
		if(b[i]>b[m])
			m=i;
	}
	fout<<b[m]<<"\n";
	while(m!=-1)
	{
		fout<<a[m]<<" ";
		m=s[m];
	}
	fout<<"\n";
	return 0;
}