Cod sursa(job #336667)

Utilizator pykhNeagoe Alexandru pykh Data 1 august 2009 01:08:56
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<fstream.h>
#define N 100005
	ifstream f("scmax.in");
	ofstream g("scmax.out");
int v[N], best[N], maxim, n, i,max1=0;

int max(int poz)
	{int sol=0, j;
		for(j=poz+1;j<=n;j++)
				if(v[j]>v[poz] && best[j]>best[sol])sol=j;	
		return sol;
}

void dinamic()
	{int k;
		for(i=n;i>=1;--i)
		{
		k=max( i);
		if(!k)best[i]=1;
		else 	{
			best[i]=best[k]+1; 
			if(best[i]>max1)
				{
					max1=best[i];
					maxim=i;}}
			}
	}
	
void afisare()

	{int k=best[maxim];
		g<<best[maxim]<<"\n";
		for(i=1;i<=n && k;i++)
			if(best[i]==k){g<<v[i]<<" ";--k;}
	}
	
int main()
	{
		freopen("scmax.in","r",stdin);
		freopen("scmax.out","w",stdout);
		f>>n;
		for(i=1;i<=n;i++)
			f>>v[i];
		dinamic();
		afisare();
		return 0;
}