Cod sursa(job #1482891)

Utilizator BodStfBodoarca Stefan BodStf Data 8 septembrie 2015 11:44:33
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include<stdio.h>

#define MAX 100001
int a[MAX],sol[MAX],N,length[MAX],best,poz[MAX];

int verifica(int i)
{
	for(int k=0;k<i;k++)
		if(sol[k]>=sol[i])
			return 0;
	return 1;
}

void bt(int i,int start)
{
	if(start==N-1)
	{
		if(best<i)
		{
			best=i;
			for(int k=0;k<i;k++)
			   length[k]=sol[k];
		}
	}

	if(i)
		start=poz[i-1]+1;
	for(int p=start;p<N;p++)
	{
		sol[i]=a[p];
		poz[i]=p;
		if(verifica(i))
			bt(i+1,start);
	}
}

int main()
{
	FILE* f1,*f2;
	f1=fopen("scmax.in","r");
	f2=fopen("scmax.out","w");
	fscanf(f1,"%d",&N);
	for(int i=0;i<N;i++)
		fscanf(f1,"%d",&a[i]);
	bt(0,0);
	fprintf(f2,"%d\n",best);
	for(int i=0;i<best;i++)
		fprintf(f2,"%d ",length[i]);
	fcloseall();
	return 0;
}