Cod sursa(job #628459)

Utilizator wink.itsgoneDragusanu Ana wink.itsgone Data 1 noiembrie 2011 14:22:18
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include<fstream.h>
#define NMAX 100001
ifstream f("scmax.in");
ofstream g("scmax.out");
int a[NMAX],best[NMAX],prec[NMAX],b[NMAX];
int n,i,m, poz,j,nr;
int main()
{
 f>>n;
 for(i=1;i<=n;i++) f>>a[i];
 best[1]=1; prec[1]=0;
 for(i=2;i<=n;i++) 
	{m=0;
	 for(j=1; j<i; j++)
		if(a[j]<a[i] && m<best[j]) { m=best[j]; poz=j; };
	 if(m==0) {best[i]=1; prec[i]=0; }
		else {best[i]=1+m; prec[i]=poz; }
	}
 poz=1;
 for(i=2;i<=n;i++)
	if(best[poz]<best[i]) poz=i;
 nr=1; b[1]=a[poz];
 g<<best[poz]<<'\n';
 do
	{
	 poz=prec[poz];
	 b[++nr]=a[poz];
	}
 while(best[poz]>1);
 for(i=nr;i>=1;i--) g<<b[i]<<' ';
 g<<'\n';
 g.close(); return 0;
}