Cod sursa(job #398427)

Utilizator rares192Preda Rares Mihai rares192 Data 18 februarie 2010 17:53:48
Problema Subsir crescator maximal Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
using namespace std;

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

long l[100000], poz[100000], a[100000], mmax, pozmax, poz1,maxf;

int main()
{
	long i, n, j;
	fin>>n;
	for(i=0; i<n; i++)
		fin>>a[i];
	
	l[n-1]=1; 
	poz[n-1]=-1;
	
	for(i=n-2; i>=0; i--)
	{
		mmax=-12;
		l[i]=1; poz[i]=-1;
		for(j=i+1; j<=n-1; j++)
	    {
				if(a[i]<=a[j] && l[i]<l[j]+1)
				{
					l[i]=l[j]+1;
					poz[i]=j;
				}
				if(mmax<l[i])
				{
					mmax=l[i];
					poz1=i;
				}
		}
		if(mmax>maxf)
		{
			maxf=mmax;
			pozmax=poz1;
		}
	}
	
		
	fout<<maxf<<'\n';
	
	
	for(i=pozmax; i!=-1; i=poz[i])
			fout<<a[i]<<" ";
return 0;
}