Cod sursa(job #2499340)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 25 noiembrie 2019 21:49:11
Problema Subsir crescator maximal Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include<stdio.h>

#define NMAX 100003

#pragma warning(push)
#pragma warning(disable: 4996)

int lung_max[NMAX], numere[NMAX], pozitii[NMAX], lungime_maxima_subsir, nr, p;


int main() {
	freopen("scmax.in", "r", stdin);
	freopen("scmax.out", "w", stdout);

	scanf("%d", &nr);
	for (int i = 0; i < nr; ++i)
	{
		scanf("%d", &numere[i]);
	}

	lung_max[nr - 1] = 1;
	pozitii[nr - 1] = -1;
	lungime_maxima_subsir = 1;
	p = nr - 1;
	for (int i = nr - 2; i >= 0; --i)
	{
		lung_max[i] = 1;
		pozitii[i] = -1;
		for (int j = i + 1; j <= nr - 1; ++j)
		{
			if (numere[i] < numere[j] && lung_max[i] < lung_max[j] + 1)
			{
				lung_max[i] = lung_max[j] + 1;
				pozitii[i] = j;
				if (lung_max[i] > lungime_maxima_subsir)
				{
					lungime_maxima_subsir = lung_max[i];
					p = i;
				}
			}
		}
	}
	
	printf("%d\n", lungime_maxima_subsir);

	int x = p;
	while (x != -1)
	{
		printf("%d ", numere[x]);
		x = pozitii[x];
	}
	

	return 0;
}

#pragma warning(pop)