Cod sursa(job #563296)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 24 martie 2011 21:37:14
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include<fstream>
using namespace std;
fstream f1,f2;
int a[100001],b[100001],c[100001],n;
int i,j,lmax,poz,lc, pozmax;
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; pozmax=0;
	for (i=n;i>=1;i--)
	{
		poz=0; lc=0;
		for (j=i+1;j<=n;j++)
		{
			if (a[i]<a[j] && b[j]>lc)
			{
				lc=b[j]; poz=j;
			}
		}
		b[i]=1+lc; c[i]=poz;
		if (b[i]>lmax)
		{
			lmax=b[i]; pozmax=i;
		}
	}
	f2<<lmax<<"\n";
	for (i=pozmax;i!=0;i=c[i])
	{
		f2<<a[i]<<" ";
	}
	f1.close();
	f2.close();
	return 0;
}