Cod sursa(job #268137)

Utilizator codrinCodrin LACHE codrin Data 28 februarie 2009 20:29:55
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<fstream.h>

void max(long a[],long n,long l[],long t[])
	{long i,j,max;
	memset(l,sizeof(l),0);
	memset(t,sizeof(t),0);
	for(i=1;i<=n;i++)
	       {max=0;
		for(j=1;j<i;j++)
		    if(a[i]>a[j]&&l[j]+1>max)
			{max=l[j];
			 t[i]=j;
			}
		l[i]=max+1;
		}
	}
int main()
{ifstream f("scmax.in");
 ofstream g("scmax.out");
long a[100000],l[100000],t[100000],i,n;
f>>n;
for(i=1;i<=n;i++)
	f>>a[i];

max(a,n,l,t);
long m=-1,ind;
for(i=1;i<=n;i++)
	if(l[i]>m)
		{m=l[i];
		 ind=i;
		}
long b[100000],j=0;
while(l[ind]>=1)
{b[++j]=a[ind];
 ind=t[ind];
}
g<<j<<"\n";
for(i=j;i>=1;i--)
	g<<b[i]<<" ";
f.close();
g.close();
return 0;
}