Cod sursa(job #539581)

Utilizator dragosd2000Dumitrache Dragos dragosd2000 Data 23 februarie 2011 08:37:45
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include<fstream.h>
ifstream fin("scmax.in");
ofstream fout("scmax.out");
int n,i,lm,a[1000],l[1000],p,x;
void citire()
{
	fin>>n>>x;
	for(i=1;i<=n;i++)
		fin>>a[i];
}
void submax()
{
	int j,max;
	l[1]=1;
	for(i=1;i<=n;i++)
	{
		max=0;
		for(j=1;j<=i;j++)
			if(l[j]>max && a[i]-a[j]>=x)
				max=l[j];
		l[i]=max+1;
		if(lm<l[i])
		{
			lm=l[i];
			p=i;
		}
	}
}
void drum( int lm, int p, int urm)
{
	if(!p)
		return ;
	if(l[p]==lm && (urm==-1 || a[p]+x<=a[urm]))// verificam daca lungimea sirului pornind de la a[p] este maxima, si daca mai exista un element anterior pentru care a[urm] sa fie mai mare sau egal cu predecesorul sau +x
	{
		
		drum(lm-1,p-1,p);
		fout<<a[p]<<' ';
		
	}
	else
		if(lm>0)
			drum(lm,p-1,urm);
}
void afisare()
{
	fout<<lm<<'\n';
}
int main()
{
	citire();
	submax();
	afisare();
	drum(lm,p,-1);// -1=urm=valoarea pe care o ia urmatorul element, adica p-1;
	return 0;
}