Cod sursa(job #478735)

Utilizator andunhillMacarescu Sebastian andunhill Data 20 august 2010 10:35:24
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,max2,ind2;
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; 
	max2=ind2=-oo;
	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;
		if(max2<s[i]) max2=s[i] , ind2=i;
	}
	g<<max2<<'\n';
	for(i=ind2;i<=N;i=pre[i])
	{	g<<a[i]<<" ";
		if(pre[i]==-1) break;
	}
	f.close();
	g.close();
	return 0;
}