Cod sursa(job #824048)

Utilizator kayhy2323Ablachim Mert-Kayhan kayhy2323 Data 25 noiembrie 2012 20:19:42
Problema Subsir crescator maximal Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.16 kb
//Ablachim Mert-Kayhan 322CA

#include<stdio.h>
#include<stdlib.h>

int cautare_binara (int *v,int *m, int a, int b, int i){
	if (a==b)
		return a;
	int mij=(a+b)/2;
	if ( v[m[mij]] < v[i] &&  v[m[mij+1]] >= v[i] )
		return mij;
	if( v[m[mij+1]] < v[i] ){
		//printf ("%d<%d\n",i,v[mij]);
		return cautare_binara(v,m,mij+1,b,i);
		
	}
	else{	//printf("%d>=%d\n",i,v[mij]);
		return cautare_binara(v,m,a,mij-1,i);
	}
}

void secv_max (int *v, int *secv,int n, int *nmax){
	int *m,*p,L=1,pred,i;
	p=malloc((n+1)*sizeof(int));
	m=malloc((n+1)*sizeof(int));
	m[0]=0;m[1]=1;v[0]=-1;
	for (i=2;i<=n;i++){
		int j=cautare_binara(v,m,0,L,i);
		m[j+1]=i;
		p[i]=m[j];
		if (L<j+1)
			L=j+1;
	}
	pred=m[L];
	*nmax=L;
	while(L){
		secv[L]=v[pred];
		pred=p[pred];
		L--;
	}
}
	
int main (int argc, char* argv[]){
	int *v,i,n,*secv,*nmax;
	FILE *f=fopen("scmax.in","r");
	FILE *g=fopen("scmax.out","w");
	nmax=malloc(sizeof(int));
	fscanf(f,"%d",&n);
	//m=malloc((n+1)*sizeof(int));
	v=malloc ((n+1)*sizeof(int));
	secv=malloc((n+1)*sizeof(int));
	for (i=1;i<=n;i++){
		//m[i]=i;
		fscanf(f,"%d",&v[i]);
	}
	
	secv_max(v,secv,n,nmax);
	for(i=1;i<=*nmax;i++)
		fprintf(g,"%d ",secv[i]);
	return 0;	
}