Cod sursa(job #478732)

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