Cod sursa(job #479945)

Utilizator andunhillMacarescu Sebastian andunhill Data 25 august 2010 19:21:17
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.64 kb
#include<fstream>
using namespace std;
#define oo 1<<30
ifstream f("scmax.in");
ofstream g("scmax.out");
int N,i,j,max1,ind,max2,ind2,k;
int a[100001],s[100001],pre[100001];
void write(int k)
{	if(pre[k]!=-1)
		write(pre[k]);
	g<<a[k]<<" ";
}
int main()
{	for(f>>N,i=1;i<=N;f>>a[i],pre[i]=-1,i++);
	s[1]=1;
	max1=1,k=1;
	for(i=2;i<=N;i++)
	{	max1=-oo;
		for(j=1;j<=i;j++)
			if(max1<s[j] && a[j]<a[i])
				max1=s[j], k=j;
		if(max1!=-oo)
		{	s[i]=1+max1;
			pre[i]=k;
		}
		else
			s[i]=1;
	}
	max1=-oo;
	for(i=1;i<=N;i++)
		if(max1<s[i])
			max1=s[i] , k=i;
	g<<max1<<'\n';
	write(k);
	f.close();
	g.close();
	return 0;
}