Cod sursa(job #1253439)

Utilizator EpictetStamatin Cristian Epictet Data 1 noiembrie 2014 12:26:35
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
using namespace std;
ifstream fin ("scmax.in");
ofstream fout ("scmax.out");
int N, ii, maxim, V[100010], PD[100010], Poz[100010];

int main()
{
	fin >> N;
	for (int i=1; i<=N; i++) fin >> V[i];
	
	for (int i=N; i>=1; i--)
	{
		PD[i] = 1;
		Poz[i] = -1;
		for (int j=i+1; j<=N; j++)
		{
			if (V[i] < V[j] && PD[i] < PD[j] + 1)
			{
				PD[i] = PD[j] + 1;
				Poz[i] = j;
			}
		}
		if (PD[i] > maxim) maxim = PD[i], ii = i;
	}
	
	
	fout << maxim << '\n' << V[ii] << ' ';
	while (Poz[ii] != -1)
	{
		ii = Poz[ii];
		fout << V[ii] << ' ';
	}

	fout.close();
	return 0;
}