Cod sursa(job #398417)

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

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

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

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--)
	{
		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;
				}
			
	    }
	}
	
	mmax=l[0], pozmax=1;
	for(i=1; i<n-1; i++)
		if(mmax<l[i])
		{
			mmax=l[i];
			pozmax=i;
		}
		
	fout<<mmax<<'\n';
	
	
	for(i=pozmax; i!=-1; i=poz[i])
			fout<<a[i]<<" ";
return 0;
}