Cod sursa(job #704573)

Utilizator gabrielvGabriel Vanca gabrielv Data 2 martie 2012 18:50:26
Problema Subsir crescator maximal Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
using namespace std;
#include<cstdio>
#define MAX 100005
int v[MAX],best[MAX],pred[MAX],rezultat[MAX];
int main()
{
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	int n,i,ant,ok=0,k,maxbest;
	scanf("%d %d",&n,&v[1]);
	best[1]=1; ant=v[1]; pred[1]=0;
	for(i=2;i<=n;i++)
	{
		scanf("%d",&v[i]);
		if(v[i]>ant)
		{
			best[i]=best[i-1]+1;
			if(!ok)
				pred[i]=i-1;
			else
			{
				pred[i]=ok;
				ok=0;
			}
		}
		else
			if(v[i]==ant)
			{
				//v[i]=-1;  // if
				best[i]=best[i-1];
				pred[i]=-1; // if
				if(!ok)
					ok=i-1;
				//else ok=ok :)
			}
			else
			{
				best[i]=1;
				pred[i]=0;
			}
		ant=v[i];
	}
	for(maxbest=0,best[0]=-1,i=1;i<=n;i++)
		if(best[i]>best[maxbest])
			maxbest=i;
	k=best[maxbest];
	printf("%d\n",best[maxbest]);
	rezultat[k--]=v[maxbest]; 
	for(i=maxbest;pred[i];i=pred[i])
		if(pred[i]!=-1)
			rezultat[k--]=v[pred[i]];	
	for(i=1;i<=best[maxbest];i++)
		printf("%d ",rezultat[i]);
	printf("\n");
	return 0;
}