Cod sursa(job #566838)

Utilizator gabriel93Robu Gabriel gabriel93 Data 29 martie 2011 12:29:54
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.51 kb
#include<fstream>
using namespace std;
fstream f1,f2;
int a[100001],b[100001],c[100001],n,i,j,l,poz,lmax,p;
int main()
{
f1.open("scmax.in",ios::in);
f2.open("scmax.out",ios::out);
f1>>n;
for(i=1;i<=n;i++)
	f1>>a[i];
lmax=0;
for(i=n;i>=1;i--)
{
	l=0;
	poz=0;
	for(j=i+1;j<=n;j++)
		if(b[j]>l&&a[j]>a[i])
		{
			l=b[j];
			poz=j;
		}
	c[i]=poz;
	b[i]=l+1;
	if(b[i]>lmax)
	{
		lmax=b[i];
		p=i;
	}
}
f2<<lmax<<"\n";
for(i=p;i!=0;i=c[i])
	f2<<a[i]<<" ";
f1.close();
f2.close();
return 0;
}