Cod sursa(job #663775)

Utilizator feelshiftFeelshift feelshift Data 18 ianuarie 2012 22:07:45
Problema Subsir crescator maximal Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
// http://infoarena.ro/problema/scmax
#include <fstream>
using namespace std;

const int MAXSIZE = 100001;

ifstream in("scmax.in");
ofstream out("scmax.out");

int length,maxim,lastPosition;
int number[MAXSIZE],best[MAXSIZE],previous[MAXSIZE];

void reconstruct(int index);

int main()
{
	in >> length;
	for(int i=1;i<=length;i++)
		in >> number[i];
	in.close();

	for(int i=2;i<=length;i++)
		for(int k=1;k<i;k++)
			if(number[k] < number[i] && best[i] < best[k] + 1)	
			{
				best[i] = best[k] + 1;
				previous[i] = k;

				if(best[i] > maxim)
				{
					maxim = best[i];
					lastPosition = i;
				}
			}

	out << ++maxim << "\n";
	reconstruct(lastPosition);

	out.close();

	return (0);
}

void reconstruct(int index)
{
	if(previous[index] != 0)
		reconstruct(previous[index]);
	out << number[index] << " ";
}