Cod sursa(job #803321)

Utilizator ArmandNMArmand Nicolicioiu ArmandNM Data 27 octombrie 2012 13:16:31
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
using namespace std;
ifstream f("scmax.in");
ofstream g("scmax.out");
int n,v[100002],lun[100002],pre[100002],predecesor,maxim1,lm,poz,i,j;

void afisare(int n, int elemente)
{
	if (elemente>0)
	{
		if (pre[n]!=0) afisare(pre[n],elemente-1);
		g<<v[n]<<" ";
	}
}

void maxim(int n)
{
	int i;
	maxim1=0;	
	for (i=1;i<=n-1;i++)
	{
		if (v[i]<v[n])
			if (lun[i]>maxim1)
			{
				maxim1=lun[i];
				predecesor=i;
			}
	}
}

int main()
{
	f>>n;
	f>>v[1];
	lun[1]=1;
	pre[1]=0;
	lm=1;
	for (i=2;i<=n;i++)
	{
		f>>v[i];
		maxim(i);
		lun[i]=1+maxim1;
		pre[i]=predecesor;
		if(lun[i]>=lm)
		{
			lm=lun[i];
			poz=i;
		}			
	}
	g<<lm<<" "<<endl;
	
//	while(pre[i]!=-1)
//{
//w[j]=v[i];
//j--;
//i=pre[i];
//}
//w[j]=v[i];
//for(i=1;i<=maxim;i++)
//g<<w[i]<<" ";
	
	afisare(poz,lm);
}