Cod sursa(job #336659)

Utilizator pykhNeagoe Alexandru pykh Data 1 august 2009 00:18:25
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<stdio.h>
#define N 100005
int v[N], best[N], maxim, n, i,max1=0;

int max(int poz)
	{int sol=0, j, lo, hi, mid, soll=0;
			lo=poz+1;
			hi=n;
         while(lo<=hi){
			 mid = lo + (hi-lo)/2;  
                     if(v[mid]<v[poz])lo=mid+1;  
					 else if(v[mid]==v[poz])return 0;
					 else if(v[mid]>v[poz]){
						if(best[mid]>=sol){hi=mid-1;soll=mid;sol=best[mid];}  
						else return soll;}
		 }  
 		 return soll;            
}

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];
		printf("%d\n",best[maxim]);
		for(i=1;i<=n && k;i++)
			if(best[i]==k){printf("%d ",v[i]);--k;}
	}
	
int main()
	{
		freopen("scmax.in","r",stdin);
		freopen("scmax.out","w",stdout);
		scanf("%d",&n);
		for(i=1;i<=n;i++)
			scanf("%d",&v[i]);
		dinamic();
		afisare();
		return 0;
}