Cod sursa(job #1096646)

Utilizator horatiu13Horatiu horatiu13 Data 2 februarie 2014 14:31:53
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#define Nmax 100005
using namespace std;

FILE *fi = fopen("scmax.in", "r");
FILE *fo = fopen("scmax.out", "w");

int v[Nmax];
int bst[Nmax];
int t[Nmax];

int n;
int mx = (1<<31);
int pmx = 0;

void afisare(int x)
{
	if (t[x]) afisare(t[x]);
	fprintf(fo, "%d ", v[x]);
}

int main()
{
	fscanf(fi, "%d", &n);
	for (int i = 1; i <= n; i++)
		fscanf(fi, "%d", &v[i]);
	
	bst[1] = 1;
	t[1] = 0;
	
	for (int i = 2; i <= n; i++)
	{
		int mx2 = 0;
		int pmx2 = 0;
		for (int j = i-1; j; j--)
		{
			if (mx2 < bst[j] && v[j] < v[i])
			{
				mx2 = bst[j];
				pmx2 = j;
			}
		}
		
		bst[i] = mx2 + 1;
		t[i] = pmx2;
		
		if (bst[i] > mx)
		{
			mx = bst[i];
			pmx = i;
		}
	}
	fprintf(fo, "%d\n", mx);
	afisare(pmx);
	return 0;
}