Cod sursa(job #357265)

Utilizator bugyBogdan Vlad bugy Data 18 octombrie 2009 17:21:20
Problema Subsir crescator maximal Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include<stdio.h>
using namespace std;
#define dim 100003

long int n,i,s,max,j,maxim,nr,x;      
int d[dim],v[dim];
long long a[dim],b[dim];

     
int quicksort(int inceput,int ultimul)      
{int i,j,temp,aux;      
  i=inceput;      
  j=ultimul;      
  temp=a[(i+j)/2];      
 do     
   {while(a[i]<temp)      i=i+1;      
    while(a[j]>temp)      j=j-1;      
    if(i<j)      
     {aux=a[i]; a[i]=a[j]; a[j]=aux;
	 aux=b[i]; b[i]=b[j]; b[j]=aux;}      
    if(i<=j)      
     {j=j-1;      
      i=i+1;      
     }      
   }while(i<=j);      
   if(inceput<j)    quicksort(inceput,j);      
   if(i<ultimul)    quicksort(i,ultimul);      
   
}  




int main()
{
	FILE *f=fopen("scmax.in","r"), *g=fopen("scmax.out","w");
	
	
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
		{fscanf(f,"%lld",&a[i]);b[i]=i;}
quicksort(1,n);
	
	for(i=1;i<=n;i++)
	{nr=1;v[1]=a[i];x=b[i];
		for(j=i+1;j<=n;j++)
			if(b[j]>x)
				{nr++;x=b[j];
			v[nr]=a[j];			
				}
				
		if(nr>max)
		{max=nr;	for(j=1;j<=nr;j++) d[j]=v[j];  }
	
	}
fprintf(g,"%d\n",max);
for(i=1;i<=max;i++)
	fprintf(g,"%d ",d[i]);
fprintf(g,"\n");

fclose(f);
fclose(g);

return 0;}