Cod sursa(job #357463)

Utilizator Bit_MasterAlexandru-Iancu Caragicu Bit_Master Data 19 octombrie 2009 12:55:32
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
//Probleme: subsiruri, decrease.

#include <cstdio>
#define N 100001

int lung_max=0,poz_lung_max;
int v[N];
int lung[N];//lung[i] = lungimea celui mai mare subsir crescator care are ultimul element v[i].
int pred[N];//pred[i] = pozitia elementului precedent elem de pe poz i in subsirul in care l-am adaugat.

void adaugare(int poz)
{
	int max_lung_pred=0; //Lungimea celui mai mare subsir anterior la care se poate lipi numarul.
	int poz_i; //Pozitia unde se gaseste ultimul element al subsirului respeciv.
	bool gasit=false;
	for (int i = 1; i <= poz; ++i)
		if ((v[i] < v [poz])&&(lung[i]>max_lung_pred))
		{
			gasit = true;
			poz_i = i;
			max_lung_pred = lung[i];
		}
	if (gasit)
	{
		lung[poz] = lung[poz_i]+1;
		pred[poz] = poz_i;
	}
	else
	{
		lung[poz] = 1;
		pred[poz] = 0;
	}
	if (lung[poz]>lung_max)
	{
		lung_max = lung[poz];
		poz_lung_max = poz;
	}
}

void printv(int poz)
{
	if (pred[poz]!=0)
		printv(pred[poz]);
	printf("%d ",v[poz]);
}

void afisare()
{
	printf("%d\n",lung[poz_lung_max]);
	printv(poz_lung_max);
}

int main()
{
	int n;
	freopen("scmax.in","r",stdin);
	freopen("scmax.out","w",stdout);
	scanf("%d",&n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d",&v[i]);
		adaugare(i);
	}
	afisare();
	return 0;
}