Cod sursa(job #522192)

Utilizator Tucu94Andrei Tuculanu Tucu94 Data 14 ianuarie 2011 15:14:06
Problema Subsir crescator maximal Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.5 kb
#include <fstream.h>
int L[100001],t[100001],v[100001],i,j,max,p,n,k,s[100001];
ifstream f("scmax.in");
ofstream g("scmax.out");
int main (){

f >> n;
for(i=1;i<=n;i++)
	f>> v[i];
 
L[1]=1;
for(i=2;i<=n;i++){
	max=0;
	p=0;
	for(j=1;j<i;j++){
		if(v[j]<v[i]&&L[j]>max){
			max=L[j];
			p=j;
		}
		L[i]=1+max;
		t[i]=p;
	}
}
for(i=1;i<=n;i++){
	if(L[i]>max)
		max=L[i];
	j=i;
}
	g<<max<<"\n";
	i=j;
while (i){
	s[++k]=v[i];
	i=t[i];
}
	for(;k>0;k--)
		g<< s[k]<<' ';

return 0;
}